首页 编程 Leetcode

# 一、理论基础

几乎无。只要记住数组是相同类型、连续存储、支持随机访问的。

# 二、题目实践

# 1、704. 二分查找

#双指针

没啥难度的，基本一次过，以下是个人版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(target == nums[mid]) {
                return mid;
            } else if(target < nums[mid]) {
                right = mid-1;
            } else if(target > nums[mid]) {
                left = mid+1;
            }
        } return -1;
    }
};

# 2、27. 移除元素

#双指针 #快慢指针

作为 “老狐狸”，重刷这道题的时候一上来的思路就是双指针，左指针从左到右找到第一个值为 val 的位置，右指针从右到左找到第一个不为 val 的位置，然后交换左右指针的值。右指针移动过的次数即为 val 的个数，用数组长度减去该值即结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size() == 1) { return nums[0] == val ? 0 : 1; }
        int ret = 0;
        int left = 0;
        int right = nums.size() - 1;
        while(left <= right) {
            while(nums[right] == val && left < right) {
                ret++;
                right--;
            }
            while(nums[left] != val && left < right) left++;
            if(left == right) {
                return nums[left] == val ? (nums.size() - ret - 1) : (nums.size() - ret);
            }
            if(nums[left] == val && nums[right] != val) {
                nums[left] = nums[right];
                nums[right] = val;
                ret++;
                left++;
                right--;
            }
        } return (nums.size() - ret);
    }
};

上上次做这道题，则是把上面这个步骤拆分成两次循环，第二次循环用于得到 val 的数量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length = nums.size();
        for(int head = 0, tail = length - 1; head < tail;) {
            if(nums[head] != val) ++head;
            if(nums[tail] == val) --tail;
            if(nums[head] == val && nums[tail] != val && head < tail) {
                nums[head] = nums[tail];
                nums[tail] = val;
            }
        }
        
        int valCount = 0;
        for(int tail = length - 1; tail >= 0 && nums[tail] == val; --tail) {
            ++valCount;
        } return (length - valCount);
    }
};

然而，针对这种思路，由于其实我们不需要考虑 k 以外的数据，所以不需要把左边的值交换 / 备份到右边，只需要不断更新左边的值即可。这样我们可以简化上面的代码，得到：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0, right = nums.size();
        while(left < right) {
            if(nums[left] == val) {
                nums[left] = nums[right - 1];  // 如果从右边赋值过来的仍然是 val，不 care，下一轮会继续处理 left
                right--;
            } else {
                left++;
            }
        } return left;
    }
};

除了双指针，其实这题用快慢指针也可以。
慢指针起初与快指针同频，当快指针遇到 val 时，慢指针停留不动，快指针继续向后寻找非 val 值。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for(int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if(val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        } return slowIndex;
    }
};

# 3、977. 有序数组的平方

#双指针

由于负数的出现，导致乍一看时没有什么多快好省的思路 pop 出来，所以先写个暴力解法压压惊：
两次循环，第一次利用 for_each 函数得到平方后的数组，第二次将平方数组排序：

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        for_each(nums.begin(), nums.end(), [](int& num) {
            return num = num*num;
        }); sort(nums.begin(), nums.end(), std::less<int>());
        return nums;
    }
};

稍作思考，想出来的仍然是双指针：
由于是升序数组，且可能存在负数，故先找到 “中心点”，即绝对值最小的位置。
然后双指针从中心向左右两边扩散，逐个比较左指针和右指针所指向的数组元素的平方大小，然后压入 vec 中。
（注意，一次比较不能把两个参与比较的值都依次压入，因为可能存在连续相同的值，如： [-10,-8,-7,-5,1,1,10] ）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left = 0;
        while(left < nums.size() && nums[left] < 0) left++;
        int right = left--;

        vector<int> ret;
        for(; left >= 0 && right < nums.size(); ) {
            int left_s = nums[left]*nums[left];
            int right_s = nums[right]*nums[right];
            if(left_s < right_s) {
                ret.push_back(left_s);
                left--;
            } else {
                ret.push_back(right_s);
                right++;
            }
        }

        for(; left >= 0; left--) {
            ret.push_back(nums[left]*nums[left]);
        }

        for(; right < nums.size(); right++) {
            ret.push_back(nums[right]*nums[right]);
        }

        return ret;
    }
};

其实，进一步地，还能优化。我们不必要执着于找到绝对值最小的位置，我们可以直接从左右两边开始，向中心收缩 —— 因为左右两边的绝对值是最大的。于是有：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int fill = nums.size() - 1;
        vector<int> result(nums.size(), 0);
        for(int i = 0, j = nums.size() - 1; i <= j; ) { // 注意这里要 i <= j，二者相等时我们正在处理最小值
            if(nums[i] * nums[i] < nums[j] * nums[j])  {
                result[fill--] = nums[j] * nums[j];
                j--;
            } else {
                result[fill--] = nums[i] * nums[i];
                i++;
            }
        } return result;
    }
};

# 4、209. 长度最小的子数组

#双指针 #滑动窗口

思路还是蛮容易想到的，还是双指针，又或者说是滑动窗口。
左右指针均从左向右滑动，当二者形成的窗口序列和大于 target 时，左指针开始向左移动以缩小窗口（直到序列和再一次小于 target 为止）。而当序列和小于 target 时，右指针向右移动一步。右指针的右滑通过 for 循环的迭代步进即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = INT32_MAX;
        int sum = 0;
        int current_len = 0;
        int i = 0; // 滑动窗口起始位置
        for(int j = 0; j < nums.size(); j++) {
            sum += nums[j];

            while(sum >= target) {
                current_len = (j - i + 1); // 取子序列的长度
                ret = min(ret, current_len);
                sum -= nums[i++];
            }
        } return (ret == INT32_MAX ? 0 : ret);
    }
};

# 5、59. 螺旋矩阵 II

这题只想得出模拟（好像也确实只有模拟的解法），但是光想想就觉得这个逻辑很复杂，想不出来。
这里学习了个评论区大佬的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        int t = 0;      // top
        int b = n-1;    // bottom
        int l = 0;      // left
        int r = n-1;    // right
        vector<vector<int>> ret(n, vector<int>(n));
        int k = 1;
        while(k <= n*n) {
            for(int i = l; i <= r; ++i, ++k) ret[t][i] = k;
            ++t;
            for(int i = t; i <= b; ++i, ++k) ret[i][r] = k;
            --r;
            for(int i = r; i >= l; --i, ++k) ret[b][i] = k;
            --b;
            for(int i = b; i >= t; --i, ++k) ret[i][l] = k;
            ++l;
        } return ret;
    }
};

# 6、15. 三数之和

#双指针

不要因为 “两数之和” 系列的题做多了，就什么都想往哈希身上套！

  1. 思路 1：
    先对 nums 进行排序。
    然后我们使用索引 i 遍历 nums，同时，我们用两个指针 left 和 right 分别指向：i 的下一位、nums 的最后一位。
    然后就是在固定 i 的情况下，left 和 right 不断向中间收缩，内层循环控制收缩。
    在内层循环中，我们每次迭代时计算三个数之和，如果结果大于零，那么 right 指针向左，如果结果小于零，那么 left 指针向右。（这个需要建立在数组递增的情况下，所以需要先对数组进行排序！）

这里需要解决重复的问题，有两种情况：
第一种情况是，在 i 固定的情况下，left 和 right 所指向的内容重复了，导致整体重复。需要在找到 left 和 right 时顺便把重复元素都剔除；（剔除之后记得同时收缩 left 和 right，以退出内层循环）
第二种情况是，虽然在第一种情况剔除了 left 和 right 遇到的重复，但是 i 在下一轮循环中重复了。故需要在进行内层循环前把重复的 i 剔除；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;

            for(int left = i + 1, right = nums.size() - 1; left < right; ) {
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0) {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    // break;
                    while(left < right && nums[left] == nums[left+1]) ++left;
                    while(left < right && nums[right] == nums[right-1]) --right;

                    --right;
                    ++left;
                } else if (sum < 0) {
                    ++left;
                } else if (sum > 0) {
                    --right;
                }
            }
        } return ret;
    }
};

# 7、18. 四数之和

#双指针

基本上就是在 “三数之和” 的基础上再套一层循环（虽然听起来很逆天，但是它确实是比直接暴力解要快）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            // if(nums[i] > target && nums[i] >= 0) break;  // 剪枝
            for(int j = i + 1; j < nums.size(); j++) {
                if(j > i + 1 && nums[j] == nums[j-1]) continue;  // 注意不能忽略 j > i + 1
                // if(nums[j] > target && nums[j] >= 0) break;  // 剪枝
                for(int left = j + 1, right = nums.size() - 1; left < right; ) {
                    // int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if((long)nums[i] + nums[j] + nums[left] + nums[right] < target) {
                        ++left;
                    } else if ((long)nums[i] + nums[j] + nums[left] + nums[right] > target) {
                        --right;
                    } else {
                        ret.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while(left < right && nums[left] == nums[left+1]) ++left;
                        while(left < right && nums[right] == nums[right-1]) --right;

                        --right;
                        ++left;
                    }
                }
            }
        } return ret;
    }
};

这里有几个细节要注意：
首先，在第二层循环 j 中，对于重复元素的判断，条件仍然需要从 j > i + 1 开始，不然会用力过度，把 2 + 2 + 2 + 2 = 8 的这种测试用例给剔除掉。
其次，四个数字相加，测试用例给的数字较大，会导致加法溢出。这里导致我出错好几次。要解决这个问题，首先我们不要用一个 int 的 sum 来存储结果，而是现场计算之后直接拿来比较，而且需要先把第一个元素强转成 long 型然后进行计算。（不要把四个数的求和括起来然后对整体的结果再强转成 long，因为在计算的过程中就会溢出了。所以必须先对其中一个数字强转，其他数字才会被触发隐式转换）。

基础题基本就这些了，可以看到数组相关的题，基本就是利用双指针来解题。

更新于

请我喝杯咖啡吧~

Rick 微信支付

微信支付

Rick 支付宝

支付宝