LeetCode + 《剑指Offer II》刷题笔记。使用 C++ 和 Java 两种语言。

数组

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

剑指 Offer II 006. 排序数组中两个数字之和

二分查找

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

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

注意：这边的int mid=low+((high-low)>>1);一定要给(high-low)>>1加()，否则执行代码会报错：超出时间限制。

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(1)

双指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int i=0,j=numbers.size()-1;
        while(i!=j){
            int sum=numbers[i]+numbers[j];
            if(sum==target){
                return {i,j};
            }else if(sum>target){
                j--;
            }else{
                i++;
            }
        }
        return {-1,-1};
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left=0,right=numbers.length-1;
        while(left<right){
            int sum=numbers[left]+numbers[right];
            if(sum==target){
                return new int[]{left,right};
            }else if(sum<target){
                left+=1;
            }else{
                right-=1;
            }
        }
        return new int[]{-1,-1};
    }
}

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

剑指 Offer II 007. 数组中和为 0 的三个数

所有和为 0 且 不重复 的三元组，故难点在于如何去除重复解。

前面提到需要使用两个指针来找出和为给定值的两个数字。在找到一个和为0的三元组之后，就需要移动这两个指针，以便找出其他符合条件的三元组。在移动指针的时候需要跳过所有相同的值，以便过滤掉重复的三元组。

 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
32
33
34
35
36

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> &nums)
    {
        vector<vector<int>> result;
        if (nums.size() >= 3){
            sort(nums.begin(), nums.end());
            int i = 0;
            while (i < nums.size() - 2){
                int j = i + 1, k = nums.size() - 1;
                while (j < k){
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum == 0){
                        result.push_back({nums[i], nums[j], nums[k]});
                        int temp = nums[j];
                        while (nums[j] == temp && j < k){
                            j++;
                        }
                    }
                    else if (sum < 0){
                        j++;
                    }
                    else{
                        k--;
                    }
                }
                int temp = nums[i];
                while (i < nums.size() && nums[i] == temp){
                    i++;
                }
            }
        }
        return result;
    }
};

由于要避免重复的三元组，因此使用一个while循环让下标j跳过重复的数字，一个while循环让下标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
28
29
30
31

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result=new LinkedList<List<Integer>>();
        if(nums.length>=3){
            Arrays.sort(nums);
            int i=0;
            while(i<nums.length){
                int j=i+1,k=nums.length-1;
                while(j<k){
                    int sum=nums[i]+nums[j]+nums[k];
                    if(sum==0){
                        result.add(Arrays.asList(nums[i],nums[j],nums[k]));
                        int temp=nums[j];
                        while(j<k && nums[j]==temp){
                            j++;
                        }
                    }else if(sum<0){
                        j++;
                    }else{
                        k--;
                    }
                }
                int temp=nums[i];
                while(i<nums.length && nums[i]==temp){
                    i++;
                }
            }
        }
        return result;
    }
}
  • 时间复杂度：O(nlogn+n^2)即O(n^2)
  • 空间复杂度：O(1)

008. 和大于等于 target 的最短子数组

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

暴力法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //暴力法 
      	int n=nums.size();
        int minLen=n+1;
        for(int i=0;i<n;i++){
            int sum=0;
            for(int j=i;j<n;j++){
                sum+=nums[j];
                if(sum>=target){
                    minLen=min(minLen,j-i+1);
                    //注意这边有个break
                    break;
                }
            }
        }
        return minLen==n+1?0:minLen;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

前缀和 + 二分查找

给定一个含有 n 个正整数的数组和一个正整数 target 。

注意这里数组中的数都是正整数，故前缀和一定是递增的，可以利用二分查找。

 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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        //前缀和 
        int n=nums.size();
        vector<int> preSum(n+1,0);
        //preSum 初始化为 n+1 大小
        //preSum[0] = 0 意味着前 0 个元素的前缀和为 0
        //preSum[i] 表示从 nums[0] 到 nums[i−1] 的元素和
        //index: 0 1 2 3 4 5
        //nums:  2 3 1 2 4 3
        //preSum:0 2 5 6 8 12 15
        for(int i=1;i<=n;i++){
            preSum[i]=preSum[i-1]+nums[i-1];
        }
        //sum[i,j]=preSum[j+1]-preSum[i]
        //sum[1,3]=6=8-2
        int minLen=n+1;
        for(int i=1;i<=n;i++){
            int temp=target+preSum[i-1];
            auto bound=lower_bound(preSum.begin(),preSum.end(),temp);
            if(bound!=preSum.end()){
                minLen=min(minLen,static_cast<int>((bound-preSum.begin())-(i-1)));
            }
        }
        return minLen==n+1?0:minLen;
    }
};

可以使用现成的库和函数来实现二分查找大于等于>=某个数的第一个位置：

  • C++ 的 lower_bound

  • Java 中的 Arrays.binarySearch

  • C# 中的 Array.BinarySearch

  • Python 中的 bisect.bisect_left

时间复杂度：

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)，额外创建数组preSum存储前缀和。

滑动窗口(双指针)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int minLen=n+1;
        int start=0,end=0;
        int sum=0;
        while(end<n){
            sum+=nums[end];
          	//注意这里是while循环
            while(sum>=target){
                minLen=min(minLen,end-start+1);
                sum-=nums[start];
                start++;
            }
            end++;
        }
        return minLen==n+1?0:minLen;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n=nums.length;
        int minLen=n+1;
        int left=0,sum=0;
        for(int right=0;right<n;right++){
            sum+=nums[right];
          	//注意这里是while循环
            while(sum>=target){
                minLen=Math.min(minLen,right-left+1);
                sum-=nums[left++];
            }
        }
        return minLen==n+1?0:minLen;
    }
}

当指针P1和P2之间的子数组数字之和小于k时，向右移动指针P2，直到两个指针之间的子数组数字之和大于k，否则向右移动指针P1，直到两个指针之间的子数组数字之和小于k。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

009. 乘积小于 K 的子数组

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

滑动窗口(双指针)

 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) {
        //双指针
        int result=0;
        if(k<=1) return result;
        int left=0,prod=1;
        for(int right=0;right<nums.size();right++){
            prod*=nums[right];
            while(prod>=k){
                prod/=nums[left++];
            }
            result+=(right-left+1);
        }
        return result;
    }
};

目标是求出所有数字乘积小于k的子数组的个数，一旦向右移动指针P1到某个位置时子数组的乘积小于k，就不需要再向右移动指针P1。这是因为只要保持指针P2不动，向右移动指针P1形成的所有子数组的数字乘积就一定小于k。此时两个指针之间有多少个数字，就找到了多少个数字乘积小于k的子数组（为right−left+1个）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        long prod=1;
        int left=0;
        int count=0;
        for(int right=0;right<nums.length;right++){
            prod*=nums[right];
            while(left<=right && prod>=k){
                prod/=nums[left++];
            }
            count+=(right-left+1);
        }
        return count;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

使用双指针解决子数组之和的题有一个前提条件——数组中的所有数字都是正数。

010. 和为 k 的子数组

剑指 Offer II 010. 和为 k 的子数组

枚举

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//提交：超出时间限制
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count=0;
        for(int left=0;left<nums.size();left++){
            int sum=0;
            for(int right=left;right>=0;right--){
                sum+=nums[right];
                //[left,right] 这个子数组的和恰好为 k 。
                if(sum==k) count++;
            }
        }
        return count;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

前缀和

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

//提交：通过
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n=nums.length;
        int[] preSum=new int[n+1];
        preSum[0]=0;
        for(int i=0;i<n;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }
        int count=0;
        for(int right=1;right<=n;right++){
            for(int left=0;left<right;left++){
                if(preSum[right]-preSum[left]==k){
                    count++;
                }
            }
        }
        return count;
    }
}
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(n)

前缀和+哈希表优化

数组的前i个数字之和记为x。如果存在一个j（j＜i），数组的前j个数字之和为x-k，那么数组中从第i+1个数字开始到第j个数字结束的子数组之和为k。

这个题目需要计算和为k的子数组的个数。当扫描到数组的第i个数字并求得前i个数字之和是x时，需要知道在i之前存在多少个j并且前j个数字之和等于x-k。所以，对每个i，不但要保存前i个数字之和，还要保存每个和出现的次数。

分析到这里就会知道我们需要一个哈希表，哈希表的键是前i个数字之和，值为每个和出现的次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        mp[0]=1;
        int sum=0;
        int count=0;
        for(int num:nums){
            sum+=num;
            count+=mp[sum-k];
            mp[sum]++;
        }
        return count;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> sumToCount=new HashMap<>();
        sumToCount.put(0,1);
        int sum=0;
        int count=0;
        for(int num:nums){
            sum+=num;
            count+=sumToCount.getOrDefault(sum-k,0);
            sumToCount.put(sum,sumToCount.getOrDefault(sum,0)+1);
        }
        return count;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

011. 0 和 1 个数相同的子数组

剑指 Offer II 011. 0 和 1 个数相同的子数组

由于0 和 1 的数量相同等价于1 的数量减去 0 的数量等于 0，我们可以将数组中的 0 视作 −1，则原问题转换成求最长的连续子数组，其元素和为 0。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int sum=0;
        int maxLen=0;
        unordered_map<int,int> mp;
      	//key:累加的数字之和 value:当前数字下标
      	//当前后累加的数字之和相等即sum这个key已经在map中存在时，下标相减即为子数组的长度。
        mp[0]=-1;
        for(int i=0;i<nums.size();i++){
            sum+=(nums[i]==1?1:-1);
            if(mp.count(sum)){
                maxLen=max(maxLen,i-mp[sum]);
            }else{
                mp[sum]=i;
            }
        }
        return maxLen;
    }
};

哈希表的键是从第1个数字开始累加到当前扫描到的数字之和，而值是当前扫描的数字的下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> sumToIndex=new HashMap<>();
        sumToIndex.put(0,-1);
        int sum=0;
        int maxLen=0;
        for(int i=0;i<nums.length;i++){
            sum+=(nums[i]==1?1:-1);
            if(sumToIndex.containsKey(sum)){
                maxLen=Math.max(maxLen,i-sumToIndex.get(sum));
            }else{
                sumToIndex.put(sum,i);
            }
        }
        return maxLen;
    }
}
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

012. 左右两边子数组的和相等

剑指 Offer II 012. 左右两边子数组的和相等

013. 二维子矩阵的和

剑指 Offer II 013. 二维子矩阵的和

1 Two Sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i=0;i<nums.size();i++){
            if(mp.find(target-nums[i])!=mp.end()){
                return vector<int>{i,mp[target-nums[i]]};
            }
            mp[nums[i]]=i;
        }
        return {};
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

3 Longest Substring Without Repeating Characters

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length()==0) return 0;
        int res=0;
        int left=0;
        unordered_set<char> temp;
        for(int i=0;i<s.length();i++){
            while(temp.find(s[i])!=temp.end()){
                temp.erase(s[left]);
                left++;
            }
            temp.insert(s[i]);
            res=max(res,i-left+1);
        }
        return res;
    }
};

注意：

这里是while循环，代码顺序很巧妙。当在set中找到当前字符的时候，需要一直erase去除最left的值，直到找不到插入，所以切记不是if循环。

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

16 3Sum Closest

 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

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int n=nums.size();
        int res=nums[0]+nums[1]+nums[2];
        for(int i=0;i<n;i++){
            int start=i+1,end=n-1;
            while(start<end){
                int sum=nums[i]+nums[start]+nums[end];
                if(abs(sum-target)<abs(res-target)){
                    res=sum;
                }
                if(sum>target){
                    end--;
                }else if(sum<target){
                    start++;
                }else{
                    return res;
                }
            }
        }
        return res;
    }
};
  • 时间复杂度：O(n^2)
  • 空间复杂度：O(1)

11 Container With Most Water

Two Pointers:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxArea(vector<int>& height) {
        int n=height.size();
        int maxArea=-1;
        int left=0,right=n-1;
        while(left<right){
            int area=min(height[left],height[right])*(right-left);
            maxArea=max(maxArea,area);
            if(height[left]<=height[right]){
                left++;
            }else{
                right--;
            }
        }
        return maxArea;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

75 Sort Colors

One Pointer:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int ptr=0;
        for(int i=0;i<n;i++){
            if(nums[i]==0){
                swap(nums[ptr],nums[i]);
                ptr++;
            }
        }
        for(int i=ptr;i<n;i++){
            if(nums[i]==1){
                swap(nums[ptr],nums[i]);
                ptr++;
            }
        }
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

Two Pointers(one-pass):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n=nums.size();
        int zero=0,two=n-1;
        for(int i=0;i<n;i++){
            while(i<=two && nums[i]==2){
                swap(nums[i],nums[two]);
                two--;
            }
            if(nums[i]==0){
                swap(nums[i],nums[zero]);
                zero++;
            }
        }
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

532 K-diff Pairs in an Array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_set<int> visited;
        unordered_set<int> res;
        for(int num:nums){
            if(visited.count(num-k)){
                res.insert(num-k);
            }
            if(visited.count(num+k)){
                res.insert(num);
            }
            visited.insert(num);
        }
        return res.size();
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

209 Minimum Size Subarray Sum

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        vector<int> preSum(n+1,0);
        for(int i=0;i<n;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }
        int res=INT_MAX;
        for(int i=1;i<=n;i++){
            int temp=target+preSum[i-1];
            auto bound=lower_bound(preSum.begin(),preSum.end(),temp);
            if(bound!=preSum.end()){
                res=min(res,static_cast<int>(bound-preSum.begin())-i+1);
            }
        }
        return res==INT_MAX?0:res;
    }
};
  • 时间复杂度：O(nlogn)
  • 空间复杂度：O(n)

Sliding Window

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n=nums.size();
        int res=INT_MAX;
        int left=0,right=0;
        int sum=0;
        while(right<n){
            sum+=nums[right];
            while(sum>=target){
                res=min(res,right-left+1);
                sum-=nums[left];
                left++;
            }
            right++;
        }
        return res==INT_MAX?0:res;
    }
};

滑动窗口看起来很简单的一个方法，但是用对了真的很巧妙。

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

523 Continuous Subarray Sum

Prefix Sum+Hash Table

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n=nums.size();
        vector<int> preSum(n+1,0);
        for(int i=0;i<n;i++){
            preSum[i+1]=preSum[i]+nums[i];
        }
        unordered_set<int> s;
        for(int i=2;i<=n;i++){
            s.insert(preSum[i-2]%k);
            if(s.count(preSum[i]%k)){
                return true;
            }
        }
        return false;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(n)