一：和为K的子数组

image-20251005140456727

1. 枚举

其实就是暴力，两层循环，python可能会超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int length = nums.size();
        int count = 0;
        for (int i = 0; i < length; ++i)
        {
            int sum = 0;
            for (int j = i; j < length; ++j)
            {
                sum += nums[j];
                if (sum == k) ++count;
            }
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraySum(int[] nums, int k) {
        int length = nums.length;
        int count = 0;
        for (int i = 0; i < length; ++i)
        {
            int sum = 0;
            for (int j = i; j < length; ++j)
            {
                sum += nums[j];
                if (sum == k) ++count;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        length = len(nums)
        count = 0
        for i in range(length):
            sum = 0
            for j in range(i, length):
                sum += nums[j]
                if (sum == k): count += 1
        return count

image-20251005142733281

2. 哈希表

遍历时记录所有和并放入哈希表，寻找子串时只寻找当前值与目标值的差，相同值通过哈希表的值来记录

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) {
        unordered_map<int, int> hashMap;
        hashMap[0] = 1;         // 相同值需要
        int sum = 0;
        int count = 0;
        for (auto& num : nums)
        {
            sum += num;
            if (hashMap.count(sum - k)) count += hashMap[sum - k];
            ++hashMap[sum];
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> hashMap = new HashMap<>();
        hashMap.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums)
        {
            sum += num;
            if (hashMap.containsKey(sum - k)) count += hashMap.get(sum - k);
            hashMap.put(sum, hashMap.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        hashMap = {0 : 1}
        sum = 0
        count = 0
        for num in nums:
            sum += num
            if (sum - k in hashMap): count += hashMap[sum - k]
            hashMap[sum] = hashMap.get(sum, 0) + 1
        return count

image-20251005142741393

二：最大子数组和

image-20251005151443719

1. 动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int next = 0;
        int result = nums[0];
        for (auto& num : nums)
        {
            next = max(next + num, num);            // 局部最优
            result = max(result, next);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int next = 0;
        int result = nums[0];
        for (int num : nums)
        {
            next = Math.max(next + num, num);            // 局部最优
            result = Math.max(result, next);
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        next = 0
        result = nums[0]
        for num in nums:
            next = max(next + num, num)          
            result = max(result, next)
        return result

image-20251005151518492

2. 分治

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:
    struct Status {
        int left, right, media, sum;
    };

    int maxSubArray(vector<int>& nums) {
        return recursion(nums, 0, nums.size() - 1).media;
    }

    Status recursion(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = ((r - l) >> 1) + l;
        Status lSub = recursion(a, l, m);
        Status rSub = recursion(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

        Status pushUp(Status l, Status r) {             // 关于区间合并的解决
        int iSum = l.sum + r.sum;
        int lSum = max(l.left, l.sum + r.left);
        int rSum = max(r.right, r.sum + l.right);
        int mSum = max(max(l.media, r.media), l.right + r.left);
        return (Status) {lSum, rSum, mSum, iSum};
    };
};
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
class Solution {
    public class Status {
        public int left, right, media, sum;

        public Status(int lSum, int rSum, int mSum, int iSum) {
            this.left = lSum;
            this.right = rSum;
            this.media = mSum;
            this.sum = iSum;
        }
    }

    public int maxSubArray(int[] nums) {
        return recursion(nums, 0, nums.length - 1).media;
    }

    public Status recursion(int[] a, int l, int r) {
        if (l == r) {
            return new Status (a[l], a[l], a[l], a[l]);
        }
        int m = ((r - l) >> 1) + l;
        Status lSub = recursion(a, l, m);
        Status rSub = recursion(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    public Status pushUp(Status l, Status r) {             // 关于区间合并的解决
        int iSum = l.sum + r.sum;
        int lSum = Math.max(l.left, l.sum + r.left);
        int rSum = Math.max(r.right, r.sum + l.right);
        int mSum = Math.max(Math.max(l.media, r.media), l.right + r.left);
        return new Status (lSum, rSum, mSum, iSum);
    };
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        return self.recursion(nums, 0, len(nums) - 1).media

    def recursion(self, a, l, r):
        if l == r:
            val = a[l]
            return (val, val, val, val)
        
        m = (r + l) // 2
        l_sub = self.recursion(a, l, m)
        r_sub = self.recursion(a, m + 1, r)  
        return self.pushUp(l_sub, r_sub)

    def pushUp(self, l, r):
        l_left, l_right, l_media, l_sum = l
        r_left, r_right, r_media, r_sum = r
        
        i_sum = l_sum + r_sum
        l_sum_new = max(l_left, l_sum + r_left)
        r_sum_new = max(r_right, r_sum + l_right)
        m_sum_new = max(max(l_media, r_media), l_right + r_left)
        
        return (l_sum_new, r_sum_new, m_sum_new, i_sum)

image-20251005151528461

3. 前缀法

参考第一题的第二中解法，时间和空间同动态规划方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int minV = 0, maxV = -1e9;
        int sum = 0;
        for (auto& num : nums)
        {
            sum += num;
            maxV = max(maxV, sum - minV);
            minV = min(minV , sum);
        }
        return maxV;
    }
};

三：合并区间

image-20251005162351476

1. 排序

对首元素排序，然后判断每个区间的首尾大小即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> reruslt;
        for (int i = 0; i < intervals.size(); ++i)
        {
            int left = intervals[i][0];
            int right = intervals[i][1];
            if (reruslt.size() == 0 || reruslt.back()[1] < left) reruslt.emplace_back(intervals[i]);
            else reruslt.back()[1] = max(reruslt.back()[1], right);
        } 
        return reruslt;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            public int compare(int[] interval1, int[] interval2) {
                return interval1[0] - interval2[0];
            }
        });

        List<int[]> reruslt = new ArrayList<>();
        for (int i = 0; i < intervals.length; ++i)
        {
            int left = intervals[i][0];
            int right = intervals[i][1];
            if (reruslt.size() == 0 || reruslt.get(reruslt.size() - 1)[1] < left) reruslt.add(new int[]{left, right});
            else reruslt.get(reruslt.size() - 1)[1] = Math.max(reruslt.get(reruslt.size() - 1)[1], right);
        } 
        return reruslt.toArray(new int[reruslt.size()][]);
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result = []
        for interval in intervals:
            if not result or result[-1][1] < interval[0]: result.append(interval)
            else: result[-1][1] = max(result[-1][1], interval[1])
        return result

image-20251005162428648

四：轮转数组

image-20251005170034155

1. 额外数组

使用一个额外数组来存储移动后的元素

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> newNums(nums.size());
        for (int i = 0; i < nums.size(); ++i)
        {
            newNums[(i + k) % nums.size()] = nums[i];
        }
        return nums.assign(newNums.begin(), newNums.end());
    }
};
1
2
3
4
5
6
7
8
9
10
class Solution {
    public void rotate(int[] nums, int k) {
        int[] newNums = new int[nums.length];
        for (int i = 0; i < nums.length; ++i)
        {
            newNums[(i + k) % nums.length] = nums[i];
        }
        System.arraycopy(newNums, 0, nums, 0, nums.length);
    }
}
1
2
3
4
5
6
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        newNums = [0] * len(nums)
        for i in range(len(nums)):
            newNums[(i + k) % len(nums)] = nums[i]
        nums[:] = newNums

image-20251005170258296

2. 环状替换

以环为单位在数组元素中跳动反转，跳转几次后会回到原点，使用临时值来作为其中一个交换对象，如果遍历交换，则需要多个值来存储交换对象，效率变低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int length = nums.size();
        k = k % length;
        int step = gcd(k, length);       // 最大公约数，得出需要的环
        for (int i = 0; i < step; ++i)
        {
            int cur = i;
            int curV = nums[i];
            do
            {
                cur = (cur + k) % length;
                swap(nums[cur], curV);
            } while(i != cur);
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int gcd(int x, int y) {
        return y > 0 ? gcd(y, x % y) : x;
    }

    public void rotate(int[] nums, int k) {
        int length = nums.length;
        k = k % length;
        int step = gcd(k, length);       // 最大公约数，得出需要的环
        for (int i = 0; i < step; ++i)
        {
            int cur = i;
            int curV = nums[i];
            do
            {
                cur = (cur + k) % length;
                int temp = nums[cur];
                nums[cur] = curV;
                curV = temp;
            } while(i != cur);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        length = len(nums)
        k = k % length
        step = math.gcd(k, length)       
        for i in range(step):
            cur = i
            curV = nums[i]
            while True:
                cur = (cur + k) % length
                nums[cur], curV = curV, nums[cur]
                if i == cur: break

image-20251005170241760

3. 数组反转

先将数组反转，然后反转前k个值，最后反转剩余值就得到换位后的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
    void reverse(vector<int>& nums, int left, int right)
    {
        for (int i = left, j = right; i < j; ++i, --j) swap(nums[i], nums[j]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
   public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int left, int right)
    {
        for (int i = left, j = right; i < j; ++i, --j)
        {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k = k % len(nums)
        self.reverse(nums, 0, len(nums) - 1)
        self.reverse(nums, 0, k - 1)
        self.reverse(nums, k, len(nums) - 1)

    def reverse(self, nums, left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

image-20251005170233096