刷个宇宙题：剑指 Offer II 006. 排序数组中两个数字之和、 007. 数组中和为 0 的三个数

题目 006. 排序数组中两个数字之和

方法1：哈希表的方式

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        //存一个key-value (值，index)
        unordered_map<int, int> ValueMap;
        int i = 0;
        for(auto num:numbers)
        {
            // ValueMap.insert(make_pair(num, i++));//插入要用make_pair 这样会出现key相同的情况
            ValueMap[num] = i++;
        }

        for(int i = 0; i<numbers.size(); i++)
        {
            if(ValueMap.find(target- numbers[i]) != ValueMap.end())
            {
                return{i, ValueMap[target-numbers[i]]};
            }
        }
        return {-1, -1};//但是这样就没有利用到排序数组这一规定
    }
};

注意，我一开始习惯用了map，但是会出现两个元素相同的情况，就会有case失败，当出现的key值已经存在时，不会再进行更新，
而用哈希表可以解决，我强行理解可能是哈希表有解决冲突的方式，但怎么存储呢……通过打印存储在map中的也只有三个值，欸这就不明白为啥了
[0,0,3,4]
0
[0,1]
it.first:4 it->second3 it.first:3it->second2 it.first:0it->second1
看代码逻辑的话，因为是按顺序是找下一个的，所以没有被存进去的那个数可以当作 被减数， 找到的那个数就是存在map中的数，逻辑就没问题了
我用map应该是也可以，只是最后遍历我用的是ValueMap，这不对，应该用numbers，所有的值都在

方法2：由于numbers是有序的，但方法1并没有利用这个特点，想到有序又是查找，用二分试试

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        //用二分法 固定一个数，找另一个数，找另一个数的方法就用二分
        for(int i = 0; i<numbers.size(); i++)
        {
            //固定的数是numbers[i]
            //用二分在剩下有序数组中找固定的值
            int low =i+1;
            int high = numbers.size()-1;
            int mid;
            while(low <= high)
            {
                mid = (high-low)/2+low;
                if(numbers[i] + numbers[mid] == target)
                {
                    return{i, mid};
                }else if(numbers[i] + numbers[mid] < target)
                {
                    low = mid+1;
                }else if(numbers[i] + numbers[mid] > target)
                {
                    high = mid-1;
                }
            }
        }
        return {-1, -1};
    }
};

方法3：双指针

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return {low, high};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return {-1, -1};
    }
};

题目 007. 数组中和为 0 的三个数

解题

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //因为不能重复，所以先进行排序，然后先固定第一个数，在后面的数组中b+c = -a的 用双指针or二分的方法
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i<nums.size(); i++)
        {
        //     if(nums[i] == nums[i++])//有可能会越界
        //     {
        //         continue;
        //     }
            if(i>0 && nums[i] == nums[i-1])//主要要写i>0 不然i-1就溢出了
            {
                continue;
            }   
            int j = i+1;
            int k = nums.size()-1;
            while(j<k)
            {
                while(j>i+1 && j<nums.size() && (nums[j] == nums[j-1]))//边界条件都很重要 如果没有j>i+1，会有case遗漏，因为j==i+1, j-1=i 就不在逻辑范围内
                {
                    j++;
                }
                if(j>=k)//注意等号
                {
                    //那就是没有数
                    break; //去下一个
                }

                if(nums[i]+nums[j]+nums[k] == 0)
                {
                    res.push_back({nums[i], nums[j],nums[k]});
                    j++;
                }else if(nums[i]+nums[j]+nums[k] > 0)
                {
                    k--;
                }else if(nums[i]+nums[j]+nums[k] < 0)
                {
                    j++;
                }
            }
        
        }
        return res;
    }
};class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        //因为不能重复，所以先进行排序，然后先固定第一个数，在后面的数组中b+c = -a的 用双指针or二分的方法
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        for(int i = 0; i<nums.size(); i++)
        {
        //     if(nums[i] == nums[i++])//有可能会越界
        //     {
        //         continue;
        //     }
            if(i>0 && nums[i] == nums[i-1])//主要要写i>0 不然i-1就溢出了
            {
                continue;
            }   
            int j = i+1;
            int k = nums.size()-1;
            while(j<k)
            {
                while(j>i+1 && j<nums.size() && (nums[j] == nums[j-1]))//边界条件都很重要 如果没有j>i+1，会有case遗漏，因为j==i+1, j-1=i 就不在逻辑范围内
                {
                    j++;
                }
                if(j>=k)//注意等号
                {
                    //那就是没有数
                    break; //去下一个
                }

                if(nums[i]+nums[j]+nums[k] == 0)
                {
                    res.push_back({nums[i], nums[j],nums[k]});
                    j++;
                }else if(nums[i]+nums[j]+nums[k] > 0)
                {
                    k--;
                }else if(nums[i]+nums[j]+nums[k] < 0)
                {
                    j++;
                }
            }
        
        }
        return res;
    }
};