LeetCode刷算法-15.三数之和

写在前面:

程序员分两种，会算法的程序员和不会算法的程序员。几乎没有一个一线互联网公司招聘任何类别的技术人员是不考算法的，程序猿们都懂的，现在最权威流行的刷题平台就是 LeetCode。

LeetCode原题链接(英文)

LeetCode原题链接(中文)

string - C++ Reference

C++中int与string的相互转换

C++ Map常见用法说明

Question: 3Sum

Difficulty:Medium Tag:Array

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

以下代码皆是本人用 C++写的，觉得还不错的话别忘了点个赞哦。各位同学们如果有其他更高效解题思路还请不吝赐教，多多学习。

A1、暴力解法

粗暴进行循环遍历，问题复杂化，不可取
Time complexity : O(n^2) 354ms，代码如下

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> temp;
        
        std::sort(nums.begin(), nums.end());
        
        map<int,int> map;
        for (int i=0; i<nums.size(); i++) {
            map[nums[i]] = i;
        }
        int index = INT32_MIN;
        for (int i=0; i<nums.size(); i++) {
            if (nums[i]>0) {
                break;
            }
            if (index == nums[i]) {
                continue;
            } else{
                index = nums[i];
            }
            int sum = -nums[i];
            
            int index1 = INT32_MIN;
            for (int j=i+1; j<nums.size(); j++) {
                if (index1 == nums[j]) {
                    continue;
                } else{
                    index1 = nums[j];
                }
                int search = sum - nums[j];
                if (map.find(search) != map.end() && map[search] > i && map[search] > j) {
                    vector<int> vec = {nums[i],nums[j],search};
                    temp.push_back(vec);
                }
            }
            
        }
        return temp;
    }
};

A2、双指针解法

减少了 map 创建，减少了部分一定不成立情况的计算，同
LeetCode刷算法题 - 11. Container With Most Water(盛最多水的容器)

算法时间复杂度 O(n^2)，Runtime: 110 ms，代码如下

int x=[](){
    std::ios::sync_with_stdio(false);  //关闭STDIN和CIN同步 减少CIN读入的时间，可以减少50%以上。
    cin.tie(NULL);
    return 0;
}();

class Solution {
public:
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        
        std::sort(nums.begin(), nums.end());
        
        int left = 0, right = (int)nums.size()-1,sum = 0;
        
        for (int i=0; i<nums.size(); i++) {
            if (nums[i]>0) break;
            if (i>0 && nums[i]==nums[i-1]) continue;
            
            sum = -nums[i];
            left = i+1;
            right = (int)nums.size()-1;
            
            while (left<right) {
                
                if (nums[left]+nums[right]==sum) {
                    vector<int> vec = {nums[i],nums[left],nums[right]};
                    res.push_back(vec);
                    
                    left++;right--;
                    
                    while (nums[left]==nums[left-1])  left++;
                    while (nums[right]==nums[right+1]) right--;
                    
                } else if (nums[left]+nums[right]>sum){
                    right--;
                    
                } else if (nums[left]+nums[right]<sum){
                    left++;
                }
            }
        }
        return res;
    }
};

引用相关

LeetCode 官网