My O(NlogN) and O(N) time complexity solution, with O(N) space


  • 21
    S

    O(NlogN): Copy the numbers and sort first, and then use two pointers to get the two numbers we want, then check the indices of these two numbers. One from head and the other from tail to avoid duplication if two numbers are the same.

    vector<int> twoSumNlogN(vector<int> &numbers, int target) {
    	vector<int> tmp = numbers;
    	sort(tmp.begin(), tmp.end());
    	int l = 0, r = (int) tmp.size() - 1;
    	while (l < r) {
    		int mid = tmp[l] + tmp[r];
    		if (mid == target) break;
    		if (mid < target) ++l; else --r;
    	}
    	
    	int index1 = 0, index2 = 0;
    	for (int i = 0; i < tmp.size(); ++i) {
    		if (numbers[i] == tmp[l]) { index1 = i; break; }
    	}
    	for (int i = (int)tmp.size() - 1; i >= 0; --i) {
    		if (numbers[i] == tmp[r]) { index2 = i; break; }
    	}
    	
    	if (index1 > index2) { index1 ^= index2; index2 ^= index1; index1 ^= index2;  }
    	vector<int> result {index1 + 1, index2 + 1};
    	return result;
    }
    

    O(N): Use map to record the index of each element, and check if the wanted complementary element exists in the map. Special process the two numbers equal situation.

    vector<int> twoSum(vector<int> &numbers, int target) {
    	int index1 = 0, index2 = 0;
    	// Special Case: target = a + a, cannot be solved by map
    	for (int i = 0; i < numbers.size(); ++i) {
    		if (numbers[i] == target / 2) {
    			if (index1 == 0) index1 = i + 1; else index2 = i + 1;
    		}
    	}
    	
    	if (index1 > 0 && index2 > 0) {
    		vector<int> result { index1, index2 };
    		return result;
    	}
    	
    	unordered_map<int, int> m;
    	for (int i = 0; i < numbers.size(); ++i) m[numbers[i]] = i + 1;
    	for (int i = 0; i < numbers.size(); ++i) {
    		if (m[target - numbers[i]] && m[target - numbers[i]] != i + 1) {
    			index1 = m[numbers[i]];
    			index2 = m[target - numbers[i]];
    			break;
    		}
    	}
    	
    	if (index1 > index2) { index1 ^= index2; index2 ^= index1; index1 ^= index2;  }
    	
    	vector<int> result { index1, index2 };
    	return result;
    }

  • 0
    J

    I think the first solution is better, although time complexity over the second.
    First step of the second seemly has solved the problem of spcial case, but when target number is odd, another special case comes out. (e.g. numbers:[3,2,1,3] target:7or5(denpeds on compiler)). If you can judge the odevity of target number prior to all acitons(e.g. if (target&1)...), the second solution would be better.


  • 0
    S

    Hi, JetQin!

    Thank you for your comment. However, the problem assumes that there is only one solution for each case, so when the target is odd, the overwritten of duplicated elements in map will not influence the correctness of answer.


  • 0
    W

    Your second solution is not O(N) because the operator [] of unordered_map is not O(1)


  • 0
    H
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with elaborating thoughts. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info. Take a look at this question post as reference.


  • -3
    H

    Similar Idea, having O(n) complexity, but less effort:

    class Solution {
    public:
        vector<int> twoSum(vector<int> &numbers, int target) {
            unordered_map<int, bool> m;
    
            for (int i = 0; i < numbers.size(); ++i) 
                m[numbers[i]] = false; // initialization
            for (int i = 0; i < numbers.size(); ++i) 
            {
             if (m[target - numbers[i]])
                {
                    int j;
                    for (j=0; j < i && numbers[j]!=target-numbers[i]; j++);
                    vector<int> result {j+1, i+1};
                    return result;
                }
                m[numbers[i]] = true;
            }
        }
    };
    

  • 0
    B

    In the first solution, it's better to use binary search to get the result more quickly instead of moving the "l" and "r" one by one step after sorted the vector.


  • 0
    A

    what about [0,1,0,2,3,0] and the target is 0 in the first solution??


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.