LEETCODE刷题笔记（剑指II）day3

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

排序+双指针

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边界条件的判断

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之间的数字个数，对应着满足条件的不同长度的数组数量。

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;
    }
};

小结：关于连续子数组的问题，如果符号一致，考虑滑动窗口，关键在滑动窗口的滑动条件

最后

以上就是爱听歌丝袜为你收集整理的LEETCODE刷题笔记（剑指II）day3的全部内容，希望文章能够帮你解决LEETCODE刷题笔记（剑指II）day3所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。