寫在前面:

程序員分兩種，會(huì)算法的程序員和不會(huì)算法的程序員。幾乎沒有一個(gè)一線互聯(lián)網(wǎng)公司招聘任何類別的技術(shù)人員是不考算法的，程序猿們都懂的，現(xiàn)在最權(quán)威流行的刷題平臺就是 LeetCode。

LeetCode原題鏈接(英文)

LeetCode原題鏈接(中文)

string - C++ Reference

C++中int與string的相互轉(zhuǎn)換

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++寫的，覺得還不錯(cuò)的話別忘了點(diǎn)個(gè)贊哦。各位同學(xué)們?nèi)绻衅渌咝Ы忸}思路還請不吝賜教，多多學(xué)習(xí)。

A1、暴力解法

粗暴進(jìn)行循環(huán)遍歷，問題復(fù)雜化，不可取
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 創(chuàng)建，減少了部分一定不成立情況的計(jì)算，同
LeetCode刷算法題 - 11. Container With Most Water(盛最多水的容器)

算法時(shí)間復(fù)雜度 O(n^2)，Runtime: 110 ms，代碼如下

int x=[](){
    std::ios::sync_with_stdio(false);  //關(guān)閉STDIN和CIN同步 減少CIN讀入的時(shí)間，可以減少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;
    }
};

引用相關(guān)

LeetCode 官網(wǎng)