Onwaier's Blog

40. 组合总和 II - 力扣（LeetCode）

发表于 2019-09-13 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例 1: 输入: candidates = [10,1,2,7,6,1,5], target = 8, 所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] 示例 2: 输入: candidates = [2,5,2,1,2], target = 5, 所求解集为: [ [1,2,2], [5] ]

题解

此题与“组合之和”一题有两个不同：一是该题数组中的数字可能会重复；二是每个数字在每个组合中只能使用一次。数字重复带来的一个问题是组合可能会重复，所以需要做去重处理。同“组合之和”一题一样，这里使用的也是递归+剪枝，这里首先对数据进行排序，方便剪枝和去重。每个数字只能使用一次，可以修改递归的起点，之前是i，这里可以修改为i + 1。其它细节具体见代码。

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int>sol;
    void dfs(vector<int>& nums, int beg, int target){//递归
        for(int i = beg; i < nums.size(); ++i){
            if(target - nums[i] < 0){//之和大于则直接return
                return;
            }
            if(i > beg && nums[i] == nums[i - 1]){//去重
                continue;
            }
            sol.push_back(nums[i]);
            if(target == nums[i]){//满足条件 放到题解中
                res.push_back(sol);
                sol.pop_back();
                return;
            }
            else{
                dfs(nums, i + 1, target - nums[i]);//之和小于target，则继续向下递归，注意此时beg是从i+1开始的
                sol.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }
};

运行结果

39. 组合总和 - 力扣（LeetCode）

发表于 2019-09-11 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取。说明：所有数字（包括 target）都是正整数。解集不能包含重复的组合。示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] 示例 2: 输入: candidates = [2,3,5], target = 8, 所求解集为: [ [2,2,2,2], [2,3,3], [3,5] ]

题解

递归搜索+剪枝详细见下图，图是以示例1为例的。

代码

class Solution {
public:
    //递归+剪枝
    vector<vector<int>>res;
    vector<int>sol;
    void dfs(vector<int>& nums, int beg, int target){
        for(int i = beg; i < nums.size(); ++i){
            sol.push_back(nums[i]);
            if(target - nums[i] > 0){//继续向下搜索
                dfs(nums, i, target - nums[i]);
            }
            else if(target - nums[i] == 0){//将符合题意的解放到res中
                res.push_back(sol);
            }
            sol.pop_back();//回溯的时候记得弹出最后一个元素
            if(target - nums[i] < 0){//剪枝，如果当前的sol中所有元素之和大于target,则直接return
                return;
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        dfs(candidates, 0, target);
        return res;
    }
};

执行结果

35. 搜索插入位置 - 力扣（LeetCode）

发表于 2019-09-09 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。示例 1: 输入: [1,3,5,6], 5 输出: 2 示例 2: 输入: [1,3,5,6], 2 输出: 1 示例 3: 输入: [1,3,5,6], 7 输出: 4 示例 4: 输入: [1,3,5,6], 0 输出: 0

题解

二分法查找，不用多说，具体见代码

代码

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int beg = 0, end = nums.size() - 1;
        int mid = (beg + end) / 2;
        while(beg <= end){//二分查找法
            mid = (beg + end ) / 2;
            if(nums[mid] > target){
                end = mid - 1;
            }
            else if(nums[mid] < target){
                beg = mid + 1;
            }
            else{
                return mid;
            }
        }
        return beg;
    }
};

执行结果

优化

将mid=(beg+end) / 2改成位移运算，运算效率会高得多。另外看到一篇题解,发现自己写的二分查找还是存在许多问题，比如，这次我就在返回beg还是end犹豫了一下，虽然凭直觉选对了，但还是把循环条件改成beg < end来得好。有时间要抽空看看那篇题解，应该会受益匪浅。

执行结果

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

发表于 2019-09-08 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。如果数组中不存在目标值，返回 [-1, -1]。示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: [-1,-1]

题解

首先想到的是二分法找到一个target的值，然后再以此为起点，分别往前和往后找，确定target出现的开始位置和结束位置。但这样做的是时间度是O(logn + n)即O(n)，不符合题目中O(logn)的要求。

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int beg = 0, end = nums.size() - 1, mid, l_idx = -1, r_idx = -1;
        while(beg <= end){//二分法先找到一个target的位置
            mid = (beg + end) / 2;
            if(nums[mid] < target){
                beg = mid + 1;
            }
            else if(nums[mid] > target){
                end = mid - 1;
            }
            else{
                break;
            }
        }
        if(beg > end){
            l_idx = r_idx = -1;
        }
        else{
            //寻找起始位置
            l_idx = mid;
            while(l_idx >= 0 && nums[l_idx] == target){
                --l_idx;
            }
            ++l_idx;
            //寻找终点位置
            r_idx = mid;
            while(r_idx < nums.size() && nums[r_idx] == target){
                ++r_idx;
            }
            --r_idx;
        }
        return vector<int>{l_idx, r_idx};
    }
};

执行结果

优化

两次二分，第一次二分找到某个target的位置pos，将l_idx与r_idx的值更新为pos,然后第二次二分分为两部分：左半边二分找到target更新l_idx,beg1 > end1结束；右半边找到target更新r_idx，beg2 > end2结束。

代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int beg = 0, end = nums.size() - 1, mid, l_idx = -1, r_idx = -1;
        int beg1, end1, beg2, end2, mid1, mid2;
        while(beg <= end){
            mid = (beg + end) / 2;
            if(nums[mid] < target){
                beg = mid + 1;
            }
            else if(nums[mid] > target){
                end = mid - 1;
            }
            else{
                break;
            }
        }
        if(beg <= end){
            l_idx = mid;
            r_idx = mid;
            beg1 = beg;
            end1 = mid - 1;
            beg2 = mid + 1;
            end2 = end;
            while(beg1 <= end1){
                mid1 = (beg1 + end1) / 2;
                if(nums[mid1] < target){
                    beg1 = mid1 + 1;
                }
                else{
                    l_idx = mid1;
                    end1 = mid1 - 1;
                }
            }
            while(beg2 <= end2){
                mid2 = (beg2 + end2) / 2;
                if(nums[mid2] > target){
                    end2 = mid2 - 1;
                }
                else{
                    r_idx = mid2;
                    beg2 = mid2 + 1;
                }
            }
        }
        return vector<int>{l_idx, r_idx};
    }
};

执行结果

33. 搜索旋转排序数组 - 力扣（LeetCode）

发表于 2019-09-06 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 O(log n) 级别。示例 1: 输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4 示例 2: 输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1

题解

看到题目要求的复杂度为[latex] o(log_2n) [/latex],首先想到的二分查找法，但一般的适用场景是整体有序，对于这种情况，如果我们能确定旋转位置rotate_idx，则整个序列分成两部分：[0, rotate_idx)和[rotate_idx, nums.size())。当target >= nums[0]时target只可能出现前一部分，反之，则出现后一部分。如何确定rotate_idx？借鉴官方题解，这里也采用二分法。 [0, rotate_idx)和[rotate_idx, nums.size())有以下特点： [latex] \\begin {split} nums[0] < nums[1] < \\cdots< nums[rotate\\_idx - 1] > \\\\ nums[rotate\\_idx] <\\cdots nums[rotate_idx]即可。具体二分的方式查看代码。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        //第一步：寻找旋转点,最小元素的下标
        int beg = 0, end = nums.size() - 1, mid = (beg + end) / 2;
        int rotate_index = 0;
        if(nums.size() == 0){//特殊情况
            return -1;
        }
        while(beg <= end){
            mid = (beg + end) / 2;
            if(mid < nums.size() - 1 && nums[mid] > nums[mid + 1]){
                rotate_index = mid + 1;
                break;
            }
            else if(nums[mid] >= nums[beg]){//搜索右边序列
                beg = mid + 1;
            }
            else{//搜索左边序列
                end = mid - 1;
            }
        }
        //第二步：确认target会出现在哪个区域[0, rotate_index)或[rotate_index, nums.size())
        if(target >= nums[0]){//目标值大于nums[0]，左边查找
            beg = 0, end = (rotate_index == 0?nums.size() - 1:rotate_index - 1);  
        }
        else{
            beg = rotate_index;
            end = nums.size() - 1;
        }
        while(beg <= end){//第三步：二分查找目标值
            mid = (beg + end) / 2;
            if(nums[mid] > target){
                end = mid - 1;
            }
            else if(nums[mid] < target){
                beg = mid + 1;
            }
            else{
                return mid;
            }
        }
        if(beg > end){
            return -1;
        }
        else{
            return 0;
        }
    }
};

执行结果

31. 下一个排列 - 力扣（LeetCode）

发表于 2019-09-05 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。必须原地修改，只允许使用额外常数空间。以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

题解

这里借用官方题解的一张动图来加深理解解法。如果整个序列是降序的，则它是排列中最大字典序，没有其它排列的字典序比它还要大。那么我们第一步就是从右往左循环一遍，看是否存在nums[i - 1] < nums[i]；不存在，则直接按题意将整个序列逆序；存在，则再从右往左扫一遍，找第一个比nums[i - 1]大的数nums[j]，交换nums[i - 1]与nums[j]的位置。再把nums[i - 1]后的序列(降序)逆序为升序。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int len = nums.size(), i = len - 1;
        int j = len - 1, tmp;
        while(i > 0 &&nums[i] <= nums[i - 1]) --i;//寻找满足升序的相邻两个数
        if(i > 0){
            while(j >= 0 && nums[j] <= nums[i - 1]) --j;//找第一个比nums[i - 1]大的数，然后交换位置
            tmp = nums[i - 1];
            nums[i - 1] = nums[j];
            nums[j] = tmp;
        }
        reverse(nums.begin() + i, nums.end());//将nums[i - 1]后的序列逆序
    }
};

运行结果

27. 移除元素 - 力扣（LeetCode）

发表于 2019-09-04 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。示例 1:

1
2
3

给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。

题解

和上一题的思路基本相似统计val元素的个数，对于不等于val的元素(nums[i])找到删除val其位置（i - cnt）。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int cnt = 0, len = nums.size();
        if(len == 0){//数组长度为0直接返回0
            return 0;
        }
        for(int i = 0; i < len; ++i){
            if(nums[i] == val){//统计val出现的次数
                ++cnt;
            }
            else{
                nums[i - cnt] = nums[i];
            }
        }
        return len - cnt;
    }
};

执行结果

官方题解

同样可以采用双指针。同上一题

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int i = 0, j = 1;
        if(len == 0){//数组长度为0直接返回0
            return 0;
        }
        for(j = 0; j < len; ++j){
            if(nums[j] != val){
                nums[i] = nums[j];
                ++i;
            }
        }
        return i;
    }
};

执行结果

26. 删除排序数组中的重复项 - 力扣（LeetCode）

发表于 2019-09-04 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 示例1:

1
2
3

给定数组 nums = [1,1,2], 
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 
你不需要考虑数组中超出新长度后面的元素。

示例2：

1
2
3

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

题解

首先数组是有序的，若相邻两元素相等，则存在重复元素（计数器cnt加1）那么移除重复元素后，原位置i的元素现在应在i-cnt处，即nums[i - cnt] = nums[i]。

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size(); //获取数组长度
        int cnt = 0;//统计重复元素
        for(int i = 1; i < len; ++i){
            if(nums[i] == nums[i - 1]){//元素重复
                ++cnt;
            }
            else{
                nums[i - cnt] = nums[i];//元素前移
            }
        }
        return len - cnt;
    }
};

运行结果

官方题解

采用双指针，一个快指针j，一个慢指针i，如果相邻元素相等，j++；如果不等，则i++，并把不等的元素复制到i处即 nums[i] = nums[j]，重复相同过程，直到j指向数组末尾。

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size(); //获取数组长度
        int i = 0, j = 1;
        if(len == 0){//数组长度为0直接返回0
            return 0;
        }
        for(j = 1; j < len; ++j){
            if(nums[j] != nums[i]){//元素不等时，移动指针i，并进行复制操作。
                ++i;
                nums[i] = nums[j];
            }
        }
        return i + 1;
    }
};

执行结果

18. 四数之和 - 力扣（LeetCode）

发表于 2019-09-03 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

题解

最直接的想法当然是四重循环，暴力求解，复杂度为[latex] O(n^4) [/latex]，直接拉进小黑屋。因为做过二数之和，三数之和等题，想着能否题目转成已知的问题。因此下面的一个想法就诞生了，固定一个数a，然后问题转成求b + c + d = target - a三数之和的解，使用的方法是排序 + 双指针。然后再改变a找到所有解。

代码

时间复杂度为$o(n^3)$

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //先排序
        sort(nums.begin(), nums.end());
        int len = nums.size(),beg, end, sum;
        vector<vector<int>>res;
        for(int i = 0; i < len - 3; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){//去重
                continue;
            }
            for(int j = i + 1; j < len - 2; ++j){
                if(j > i + 1 && nums[j] == nums[j - 1]){//去重
                    continue;
                }
                beg = j + 1, end = len - 1;
                while(beg < end){
                    sum = nums[i] + nums[j] + nums[beg] + nums[end];
                    if(sum > target){
                        --end;
                        while(beg < end && nums[end] == nums[end + 1]){
                            --end;
                        }
                    }
                    else if(sum < target){
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                    else{
                        res.push_back({nums[i], nums[j], nums[beg], nums[end]});
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                }
            }
        }
        return res;
    }
};

执行结果

优化

借助大佬的思路，加入两个if判断，用时瞬间超过90%！ 1. 如果tmp = a + min{b + c + d}仍然大于target，则整个循环没有继续下去的必要了，后面的四数之和不小于tmp，即大于target。 2. 如果tmp = a + max{b + c + d}仍然小于target，则此趟循环可以continue。具体见代码

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //先排序
        sort(nums.begin(), nums.end());
        int len = nums.size(),beg, end, sum;
        vector<vector<int>>res;
        for(int i = 0; i < len - 3; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){//去重
                continue;
            }
            //当数组最小值和都大于target 跳出
            if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)
                break;
            //当数组最大值和都小于target,说明i这个数还是太小,遍历下一个
            if(nums[i] + nums[len-1] + nums[len-2] + nums[len-3] < target)
                continue;
            for(int j = i + 1; j < len - 2; ++j){
                if(j > i + 1 && nums[j] == nums[j - 1]){//去重
                    continue;
                }
                beg = j + 1, end = len - 1;
                while(beg < end){
                    sum = nums[i] + nums[j] + nums[beg] + nums[end];
                    if(sum > target){
                        --end;
                        while(beg < end && nums[end] == nums[end + 1]){
                            --end;
                        }
                    }
                    else if(sum < target){
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                    else{
                        res.push_back({nums[i], nums[j], nums[beg], nums[end]});
                        ++beg;
                        while(beg < end && nums[beg] == nums[beg - 1]){
                            ++beg;
                        }
                    }
                }
            }
        }
        return res;
    }
};

执行结果

16. 最接近的三数之和 - 力扣（LeetCode）

发表于 2019-09-03 更新于 2022-02-13 分类于 LeetCode 阅读次数： Disqus：

题目描述

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。例如，给定数组 nums = [-1，2，1，-4], 和 target = 1. 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

题解

最容易想到的方法，肯定是三重循环，暴力求解，但是时间复杂度过高为[latex] O(n^3) [/latex]。这里借鉴昨天三数之和那一题的解题思路，采用排序+双指针的方法来求解，同样a固定，然后首尾指针分别指向b与c，当a+b+c=target，则最优解就是target。若a+b+c>target，指向c的指针向左移动；若a+b+c<target，指向b的指针向右移动。当两指针相遇本次循环结束，然后更改a的位置，重复上述操作，直到找到最优解。起初，天真的以为当sum(a+b+c)由大于target转为小于target或者由小于target转为大于target时，就能找到本次循环的最优解，就能跳出循环，后来提交才发现并不是，所以还是老老实实的判断吧。

错误代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int len = nums.size(), beg, end, sum, res;
        bool posFlag = false, negFlag = false, flag = false;;
        int posSum, negSum;
        for(int i =0; i < len - 2; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){//去重
                continue;
            }
            beg = i + 1, end = len - 1;
            posFlag = false, negFlag = false;
            while(beg < end){
                sum = nums[i] + nums[beg] + nums[end];
                if(sum > target){
                    --end;
                    posFlag = true;
                    posSum = sum;
                }
                else if(sum < target){
                    ++beg;
                    negFlag = true;
                    negSum = sum;
                }
                else{
                    res = target;
                    flag = true;
                    break;
                }
                if(posFlag && negFlag){
                    if(!flag){
                        flag = true;
                        res = posSum - target > target - negSum?negSum:posSum; 
                    }
                    else{
                        int tmp = posSum - target > target - negSum?negSum:posSum; 
                        res = abs(tmp - target) > abs(res - target)?res:tmp;
                    }
                    break;
                }
            }
            if(flag && res == target){
                break;
            }
           if(posFlag && !negFlag){//全大于target，取最小
                if(i + 2 < len){
                    if(!flag){
                        flag = true;
                        res = nums[i] + nums[i + 1] + nums[i + 2];
                    }
                    else{
                        int tmp = nums[i] + nums[i + 1] + nums[i + 2];
                        res = abs(tmp - target) > abs(res - target)?res:tmp;
                    }
                }
            }
            else if(negFlag && !posFlag){//全小于target，取最大
                if(i + 2 < len){
                    if(!flag){
                        flag = true;
                        res = nums[i] + nums[len - 1] + nums[len - 2];
                    }
                    else{
                        int tmp = nums[i] + nums[len - 1] + nums[len - 2];
                        res = abs(tmp - target) > abs(res - target)?res:tmp;
                    }
                }
            }
            if(flag && res == target){
                break;
            }
        }
        return res;
    }
};
///未ac

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int len = nums.size(), beg, end, sum, res;
        for(int i =0; i < len - 2; ++i){
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            if(i == 0){
                res = nums[0] + nums[1] +nums[2];
            }
            beg = i + 1, end = len - 1;
            while(beg < end){
                sum = nums[i] + nums[beg] + nums[end];
                if(abs(sum - target) < abs(res - target)){//取距离较小的
                        res = sum;
                }
                if(sum > target){//偏大，减小end
                    --end;
                }
                else if(sum < target){//偏小，增大beg
                    ++beg;
                }
                else{//相等，找到最优解，直接返回
                    return res;
                }
            }
        }
        return res;
    }
};