【LeetCode】015 3Sum

题目：

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: 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]

]

题解：

　　对于i和j，在j+1至n中寻找符合条件的第三个值，一种方法是建立map映射表，利用map的find函数。对重复项的检测上使用了比较麻烦的方法。

Solution 1 （TLE）

 class Solution {

 public:

     vector<vector<int>> threeSum(vector<int>& nums) {

         vector<vector<int>> vv;

         vector<int> v;

         int i = , j = , n = nums.size(),tar=;

         unordered_map<int, int> m;

         for(; i<n; i++)

         //value-position

             m[nums[i]] = i;

         for(i=; i<n-; i++) {

             for(j=i+; j<n-; j++) {

                  tar =  - nums[i] - nums[j];

                 if(m.count(tar) && m[tar]>j) {

                     v.push_back(nums[i]);

                     v.push_back(nums[j]);

                     v.push_back(tar);

                     sort(v.begin(),v.end());

                     if(find(vv.begin(),vv.end(),v) == vv.end())

                         vv.push_back(v);

                         v.clear();

                 }

             }

         }

         return vv;

     }

 };

　　Solution 1 TLE的原因就在于重复字段的判断上，耗费了大量时间。那么怎么降低呢？这里有个小技巧，对于存在可重复数字的数组，往往联想到先将数组排序，这样可能会减少大量工作。于是在for循环前先将nums排序，然后在循环中对于两元素值相同的情况直接跳过，即当nums[i] == nums[i-1]时，由于nums[i-1]已经遍历完成，故跳过nums[i]，对于j（尾指针）也是同样的处理。

Solution 2 （312ms）

class Solution {

public:

   vector<vector<int>> threeSum(vector<int>& nums) {

        vector<vector<int>> vv;

        vector<int> v;

        int i = , j = , n = nums.size(),tar=;

        unordered_map<int, int> m;

        sort(nums.begin(),nums.end());

        for(; i<n; i++)

        //value-position

            m[nums[i]] = i;

        for(i=; i<n-; i++) {

            if (i> && nums[i-]==nums[i]) continue;

            for(j=i+; j<n-; j++) {

                if (j>i+ && nums[j-]==nums[j]) continue;

                 tar =  - nums[i] - nums[j];

                if(m.find(tar) != m.end() && m[tar]>j) {

                    vv.push_back({nums[i],nums[j],tar});

                }

            }

        }

        return vv;

    }

};

　　Solution 2 虽然AC了，但用时312ms，效率太低了。我们进一步进行优化。此题的思路就是在i之后的数组内寻找符合条件的两个值，Solution 1和Solution 2是将i和j固定，寻找第三个值，那么我们也可以固定i，寻找j和k来满足条件。还是先将数组排序，固定i后，j，k分别为剩余数组的头指针、尾指针，在j<k时执行搜索，直到j>=k时停止搜索。遇到重复项依然是跳过处理。

Solution 3 (119ms)

 class Solution {

 public:

     vector<vector<int> > threeSum(vector<int> &nums) {

         vector<vector<int>> vv;

         sort(nums.begin(), nums.end());

         int n = nums.size();

         for(int i=; i<n-; i++) {

             if(nums[i] > ) break;

             if(i> && nums[i] == nums[i-]) continue;

             int a = nums[i];

             int j = i+, k = n-;

             while(j<k) {

                 int b = nums[j], c = nums[k];

                 if(a+b+c == ) {

                     vv.push_back({a,b,c});

                     while(j<n && nums[j] == nums[j+]) j++; j++;

                     while(k>i && nums[k] == nums[k-]) k--; k--;

                 }

                 else if(a+b+c > ) {

                     while(k>i && nums[k] == nums[k-]) k--; k--;

                 }

                 else {

                     while(j<n && nums[j] == nums[j+]) j++; j++;

                 }

             }

         }

         return vv;

     }

 };

　　在重复项检测上也可以利用set的特性：不包含重复项。这只是一个小技巧。

Solution 4 (279ms)

class Solution {

public:

    vector<vector<int> > threeSum(vector<int> &nums) {

        set<vector<int>> sv;

        sort(nums.begin(), nums.end());

        int n = nums.size();

        for(int i=; i<n-; i++) {

            if(nums[i] > ) break;

            int a = nums[i];

            int j = i+, k = n-;

            while(j<k) {

                int b = nums[j], c = nums[k];

                if(a+b+c == ) {

                    sv.insert({a,b,c});

                    j++;

                    k--;

                }

                else if(a+b+c > ) k--;

                else j++;

            }

        }

        return vector<vector<int>> (sv.begin(),sv.end());

    }

};

巴特西

【LeetCode】015 3Sum

最新文章

热门文章