Two pointers solution


  • 2
    L

    Algo:

    1. modify the original question to this one: in an ordered array, find two numbers and their sum equals to target.
    2. two pointers. One moves from start to end, and the other moves in the opposite direction. Each time one pointer moves based on value of sum.

    class Solution {
        public:
        	vector<vector<int> > threeSum(vector<int> &num) {
        		vector< vector<int> > ans;
        		if (num.empty())
        			return ans;
    
    		sort(num.begin(), num.end());
    
    		int n = num.size();
    		for (int i = 0; i < n - 2; ++i) {
    			if (i > 0 && num[i] == num[i - 1])
    				continue;
    
    			int target = -num[i];
    			int left = i + 1, right = n - 1;
    			while (left < right) {
    				int sum = num[left] + num[right];
    				if (right < n - 1 && num[right] == num[right + 1]) {
    					--right;
    				} else if (sum > target) {
    					--right;
    				} else if (sum < target) {
    					++left;
    				} else {
    					int t[] = {num[i], num[left], num[right]};
    					ans.push_back(vector<int>(t, t + 3));
    					++left;
    					--right;
    				}
    			}
    		}
    		return move(ans);
    	}
    };

  • 1
    E

    My Answer

    public List<List<Integer>> threeSum(int[] num) {
           List<List<Integer>> result = new ArrayList<List<Integer>>();
           if(num.length<3)
    			return result;
    		Arrays.sort(num);
    		for(int i=0;i<num.length-2;i++){
    			if(i>0&&num[i]==num[i-1])
    				continue;
    			int j=i+1,k=num.length-1;
    			while(j<k){
    				if(num[i]+num[j]+num[k]==0){
    					List<Integer> list = new ArrayList<Integer>();
    					list.add(num[i]);
    					list.add(num[j]);
    					list.add(num[k]);
    					result.add(list);
    					j++;
    					k--;
    				}else if(num[j]+num[k]<-1*num[i]){
    					j++;
    				}else if(num[j]+num[k]>-1*num[i]){
    					k--;
    				}
    			}
    			
    		}
    	   Set set = new HashSet(result);
    	   List<List<Integer>> result2 = new ArrayList<List<Integer>>();
    	   for(Object e:set){
    		   result2.add((List<Integer>) e);
    	   }
    	   if(result2.isEmpty()){
    		   return result;
    	   }else
    	   return result2;
        }

Log in to reply
 

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