首页 > itarticle > yusijia’s blog Three-Sum

yusijia’s blog Three-Sum

admin 11月 12, 2020 0

Contents

/*

Given an array S of n integers, are there elements a, b, c in S such that
a + b + c = 0?
Find all unique triplets in the array which gives the sum of zero.
Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a <= b
<= c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
*/

题意：

在给定数列中找出三个数，使和为 0, 不允许重复。

分析：

先排序，再左右夹逼，复杂度 O(n*n)。
N-sum 的题目都可以用夹逼做，复杂度可以降一维。

class Solution {  
   public:  
       vector<vector<int> > threeSum(vector<int> &num) {  
           vector<vector<int> > ret;  
           int len = num.size();  
           int tar = 0;  
     
           if (len <= 2)  
               return ret;  
     
           sort(num.begin(), num.end());  
     
           for (int i = 0; i <= len - 3; i++) {  
               
               int j = i + 1;  // second number  
               int k = len - 1;    // third number  
               while (j < k) {  
                   if (num[i] + num[j] + num[k] < tar) {  
                       ++j;  
                   } else if (num[i] + num[j] + num[k] > tar) {  
                       --k;  
                   } else {  
                       ret.push_back({ num[i], num[j], num[k] });  
                       ++j;  
                       --k;  
                       // folowing 3 while can avoid the duplications  
                       while (j < k && num[j] == num[j - 1])  
                           ++j;  
                       while (j < k && num[k] == num[k + 1])  
                           --k;  
                   }  
               }  
               while (i <= len - 3 && num[i] == num[i + 1])  
                   ++i;  
           }   
           return ret;  
       }  
   };

import java.util.*;

public class  {

    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < num.length - 2 && num[i] <= 0; i++) {
            if (i > 0 && num[i] == num[i - 1])
                continue;
            int j = i + 1;
            int k = num.length - 1;
            while (j < k) {
                if (num[i] + num[j] + num[k] > 0) {
                    k--;
                } else if (num[i] + num[j] + num[k] < 0) {
                    j++;
                } else {
                    ArrayList<Integer> list = new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[j]);
                    list.add(num[k]);
                    res.add(list);
                    do {
                        j++;
                    } while (j < k && num[j] == num[j - 1]);
                    do {
                        k--;
                    } while (j < k && num[k] == num[k + 1]);
                }
            }
        }
        return res;
    }

}