leetcode 1.Two Sum 、167. Two Sum II - Input array is sorted 、15. 3Sum 、16. 3Sum Closest 、 18. 4Su...

1.two sum

用hash來存儲數值和對應的位置索引，通過target-目前值來獲得需要的值，然後再hash中尋找

錯誤代碼1：

Input:

[3,2,4]

Output:

[0,0]

Expected:

[1,2]

同一個數字不能重複使用，但這個代碼沒排除這個問題

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> m;
        for(int i = 0;i < nums.size();i++)
            m[nums[i]] = i;
        for(int i = 0;i < nums.size();i++){
            int num = target - nums[i];
            if(m.count(num)){
                result.push_back(i);
                result.push_back(m[num]);
                break;
            }
        }
        return result;
    }
};

錯誤代碼2：

Input:

[3,3]

Output:

[]

Expected:

[0,1]

可以使用相同的數字，但不能使用同一位置的數字，這個錯誤代碼實際上是針對相同數字，而不是同一位置的數字

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> m;
        for(int i = 0;i < nums.size();i++)
            m[nums[i]] = i;
        for(int i = 0;i < nums.size();i++){
            int num = target - nums[i];
            if(m.count(num) && num != nums[i]){
                result.push_back(i);
                result.push_back(m[num]);
                break;
            }
        }
        return result;
    }
};

正确代碼：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int,int> m;
        for(int i = 0;i < nums.size();i++)
            m[nums[i]] = i;
        for(int i = 0;i < nums.size();i++){
            int num = target - nums[i];
            if(m.count(num) && m[num] != i){
                result.push_back(i);
                result.push_back(m[num]);
                break;
            }
        }
        return result;
    }
};

說白了錯誤2是判斷數值相等，正确的寫法是判斷索引是否相等，就直接拒絕了這種同一個數字重複兩次的情況

167. Two Sum II

數組是有序的，是以用兩個指針從兩側向中間滑動就可以解決

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> result;
        int start = 0;
        int end = numbers.size() - 1;
        while(start < end){
            int tmp = numbers[start] + numbers[end];
            if(tmp == target){
                result.push_back(start+1);
                result.push_back(end+1);
                break;
            }
            else if(tmp < target)
                start++;
            else
                end--;
        }
        return result;
    }
};

15. 3Sum

先将數組排序，然後固定一個數，再将剩下兩個數類似于two sumII的方法在數組開始和末尾進行滑動。

因為不求重複的，是以在滑動的過程中：1.在for循環中遇到相同的數字直接continue

　　　　　　　　　　　　　　　　　　2.在while循環中也是直接++或者--

　　　　　　　　　　　　　　 3.另外如果當便利到的第一個數大于0了，那後面的數都會大于0，也就沒有了計算的意義，是以可以直接break掉

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

# 這個題必須有if(nums.size() < 3)，不然在nums為[]時就會報錯。

原因在于https://stackoverflow.com/questions/47947956/reference-binding-to-null-pointer-of-type-value-type

size()函數傳回的是無符号的，0-3會得到一個很大的數

leetcode 1.Two Sum 、167. Two Sum II - Input array is sorted 、15. 3Sum 、16. 3Sum Closest 、 18. 4Su...

16. 3Sum Closest

與3Sum類似的思路，先排序，然後固定其中一個值，再滑動另外兩個值。3Sum相等時還需要繼續移動start、end，但這個時候的比較是比較diff的最小值，滑動判斷的條件是根據sum與target的值在判斷

錯誤寫法：

認為初始sum的時候計算了第一個位置，即index=0，for循環就從index=1開始，但實際上隻計算了前三個，index=0還有很多其他的和的情況，比如index=0、index=1、index=3

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int sum = nums[0] + nums[1] + nums[2];
        int res = sum;
        int diff = abs(target - sum);
        for(int i = 1;i <= nums.size() - 3;i++){
            int start = i + 1;
            int end = nums.size() - 1;
            while(start < end){
                int sum = nums[i] + nums[start] + nums[end];
                int new_diff = abs(target - sum);
                if(new_diff < diff){
                    diff = new_diff;
                    res = sum;
                }
                if(sum < target)
                    start++;
                else
                    end--;
            }
        }
        return res;
    }
};

正确寫法：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int sum = nums[0] + nums[1] + nums[2];
        int res = sum;
        int diff = abs(target - sum);
        for(int i = 0;i <= nums.size() - 3;i++){
            int start = i + 1;
            int end = nums.size() - 1;
            while(start < end){
                int sum = nums[i] + nums[start] + nums[end];
                int new_diff = abs(target - sum);
                if(new_diff < diff){
                    diff = new_diff;
                    res = sum;
                }
                if(sum < target)
                    start++;
                else
                    end--;
            }
        }
        return res;
    }
};

18. 4Sum

這個題和3Sum很像，但3Sum的target是固定為0，4Sum是任意target。

兩者都是先排序，3Sum是固定一個數，4Sum類似于固定兩個數，即有兩個數是外層for循環。兩者都需要去重。

錯誤寫法：

j > 1,這種情況就要報錯：

Input:

[-1,0,1,2,-1,-4]

-1

Output:

[[-4,0,1,2]]

Expected:

[[-4,0,1,2],[-1,-1,0,1]]

j > 1這種寫法會把之後所有的j > 1相同的都去掉，讓後面的根本沒有進行比較

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size() < 4)
            return result;
        sort(nums.begin(),nums.end());
        for(int i = 0;i <= nums.size() - 4;i++){
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            for(int j = i + 1;j <= nums.size() - 3;j++){
                if(j > 1 && nums[j] == nums[j-1])
                    continue;
                int start = j + 1;
                int end = nums.size() - 1;
                while(start < end){
                    int sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if(sum == target){
                        vector<int> res;
                        res.push_back(nums[i]);
                        res.push_back(nums[j]);
                        res.push_back(nums[start]);
                        res.push_back(nums[end]);
                        result.push_back(res);
                        while(start < end && nums[start] == nums[start+1])
                            start++;
                        while(start < end && nums[end] == nums[end-1])
                            end--;
                        start++;
                        end--;
                    }
                    else if(sum < target)
                        start++;
                    else
                        end--;
                }               
            }
        }
        return result;
    }
};

正确寫法：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if(nums.size() < 4)
            return result;
        sort(nums.begin(),nums.end());
        for(int i = 0;i <= nums.size() - 4;i++){
            if(i > 0 && nums[i] == nums[i-1])
                continue;
            for(int j = i + 1;j <= nums.size() - 3;j++){
                if(j > 1+1 && nums[j] == nums[j-1])
                    continue;
                int start = j + 1;
                int end = nums.size() - 1;
                while(start < end){
                    int sum = nums[i] + nums[j] + nums[start] + nums[end];
                    if(sum == target){
                        vector<int> res;
                        res.push_back(nums[i]);
                        res.push_back(nums[j]);
                        res.push_back(nums[start]);
                        res.push_back(nums[end]);
                        result.push_back(res);
                        while(start < end && nums[start] == nums[start+1])
                            start++;
                        while(start < end && nums[end] == nums[end-1])
                            end--;
                        start++;
                        end--;
                    }
                    else if(sum < target)
                        start++;
                    else
                        end--;
                }               
            }
        }
        return result;
    }
};

653. Two Sum IV - Input is a BST

隻要是兩數之和的題，一定要記得先嘗試用Hash來做，這道題隻不過是把數組變成了一棵二叉樹而已，換湯不換藥。

還是用遞歸的思想，周遊到每個節點的時候，用target-目前節點的值，看hash裡面是否存儲了值。如果沒有就遞歸周遊，同時将此節點的值存儲在hash中，以便後面的值去尋找。

class Solution {
public:
    bool findTarget(TreeNode* root, int k) {
        unordered_set<int> container;
        return findTarget(root,k,container);
    }
    bool findTarget(TreeNode* root,int k,unordered_set<int>& container){
        if(root == NULL)
            return false;
        int val = k - root->val;
        if(container.count(val))
            return true;
        container.insert(root->val);
        return findTarget(root->left,k,container) || findTarget(root->right,k,container);
    }
};

454. 4Sum II

https://www.cnblogs.com/grandyang/p/6073317.html

class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> m;
        for(int i = 0;i < A.size();i++){
            for(int j = 0;j < B.size();j++){
                m[A[i] + B[j]]++;
            }
        }
        int res = 0;
        for(int i = 0;i < C.size();i++){
            for(int j = 0;j < D.size();j++){
                int tmp = -(C[i] + D[j]);
                if(m.find(tmp) != m.end())
                    res += m[tmp];
            }
        }
        return res;
    }
};

轉載于:https://www.cnblogs.com/ymjyqsx/p/9556628.html

leetcode 1.Two Sum 、167. Two Sum II - Input array is sorted 、15. 3Sum 、16. 3Sum Closest 、 18. 4Su...

繼續閱讀

goalng nil interface淺析持續學習

模組化：數學模組化

開源軟體：NoSql資料庫 - 圖資料庫 Neo4j轉載自原文位址：http://www.cnblogs.com/loveis715/p/5277051.html

資料在網絡7層中的傳輸過程

當今世界十大經典算法

字元串功能實作

【算法提高班】貪婪政策

《貪婪的動态規劃》

分治法實作求解最大子數組

UVA 10154:Weights and Measures Weights and Measures

Linux Kernel Development　學習

動态規劃、最小費用流例題 — nyoj_712 探尋寶藏

計算機開路人阿蘭·圖靈

基礎算法之二分查找

poj3249

PAT 1089 Insert or Merge[難]