LEETCODE刷题笔记（剑指II）day3

83 阅读 0 评论 55 点赞

我是靠谱客的博主爱听歌丝袜，这篇文章主要介绍LEETCODE刷题笔记（剑指II）day3，现在分享给大家，希望可以做个参考。

剑指 Offer II 007. 数组中和为 0 的三个数 - 力扣（LeetCode） (leetcode-cn.com)

排序+双指针

复制代码

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>> threeSum(vector<int>& nums) {
        vector<vector<int> > res;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n; ++i) {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int l = i + 1, r = n - 1;
            while(l < r) {
                if(l > i + 1 && nums[l] == nums[l - 1]) {
                    ++l;
                    continue;
                }
                int sumn = nums[i] + nums[l] + nums[r];
                if(sumn > 0) {
                    --r;
                    continue;
                } else if(sumn < 0) {
                    ++l;
                    continue;
                } else {
                    res.push_back({nums[i], nums[l], nums[r]});
                    ++l;
                }
            }
        }
        return res;
    }
};

剑指 Offer II 008. 和大于等于 target 的最短子数组

滑动窗口，注意left，right边界条件的判断

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int Sum = 0, l = 0, r = 0, minLen = INT_MAX;
        while(l < n && r <= n) {
            while(Sum < target && r < n) {
                Sum += nums[r];
                ++r;
            }
            if(Sum >= target) {
                int len = r - l;
                minLen = min(len, minLen);
            }
            Sum -= nums[l];
            ++l;
            if(minLen == 1) return minLen;
        }
        return minLen == INT_MAX? 0 : minLen;
    }
};

剑指 Offer II 009. 乘积小于 K 的子数组

滑动窗口

枚举r，找到满足条件的最小的l

r-l+1 = 从l到r之间的数字个数，对应着满足条件的不同长度的数组数量。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        if(k <= 1) return 0; 
        int pro = 1;
        int ans = 0, l = 0;
        for(int r = 0; r < nums.size(); ++r) {
            pro *= nums[r];
            while(pro >= k) {
                pro /= nums[l];
                ++l;
            }
            ans += r - l + 1;
        }
        return ans;
    }
};