3Sum - 每日算法

每日算法——letcode系列

问题 Longest Common Prefix

Difficulty: Medium

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.

<pre>
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:(-1, 0, 1)(-1, -1, 2)

</pre>

class Solution {public:    vector<vector<int>> threeSum(vector<int>& nums) {}};

翻译

三数和

难度系数：中等

给定一个有n个整数的数组S, 判断是否存在a, b, c三个元素满足a + b + c = 0? 找到数组中所有满足和为零的三个数（数组中不能有重复的三个数） 。

思路

如果随机找$C_n^3$种方案。假定满足条件的三个数为a,b,c，这三个数索引分别为i, j, k。先排序，从数组的头确定一个数a，b的索引比a大1，c为数组的尾，有三种情况

• a + b + c = target 则i++ k-- 并把这三个数记录下来

• a + b + c < target 则j++

• a + b + c < target 则k--
  终止条件b < c。

相当于确定两个，动一个，这样比较好确定方案

代码

class Solution {public:    vector<vector<int>> threeSum(vector<int> &nums) {        vector<vector<int> > result;    // 排序        sort(nums.begin(), nums.end());        int n = static_cast<int>(nums.size());    for (int i = 0; i < n - 2; ++i) {// 去重复// 下面注释掉的去重复方案是错误的， 会把0，0，0也去掉//while (i < n -2 && nums[i] == nums[i+1]) {//    i++;//} if (i>0 && nums[i-1] == nums[i]){     continue; }int j = i + 1;int k = n - 1;while (j < k) {    if (nums[i] + nums[j] + nums[k] < 0){        // 去重复        while (j < k && nums[j] == nums[j+1]) {j++;        }        j++;    }    else if (nums[i] + nums[j] + nums[k] > 0){         // 去重复        while (k > j && nums[k] == nums[k-1]) {k--;        }        k--;    }    else{        result.push_back({nums[i], nums[j], nums[k]});        // 去重复        while (j < k && nums[j] == nums[j+1]) {j++;        }        while (k > j && nums[k] == nums[k-1]) {k--;        }        j++;        k--;    }}        }        return result;    }};