自定义

# 1. 两数之和 - 力扣（LeetCode） (opens new window)

# 哈希表

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> hashtable = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            } else {
                hashtable.put(nums[i],i);
            }
        }
        return new int[0];
    }
}

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

# 560. 和为 K 的子数组 - 力扣（LeetCode） (opens new window)

# 前缀和

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 子数组 [j, i] 的和可表示为 sum[i] - sum[j-1] = k → 等价于 sum[j-1] = sum[i] - k
        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        // 初始化：前缀和为0出现1次
        prefixSumMap.put(0, 1);
        int sum = 0;
        int count = 0;
        for (int num : nums) {
            sum += num;
            // sum - k 代表在位置 i 之前，是否存在某个前缀和 sum[j] 等于当前前缀和减去 k
            if (prefixSumMap.containsKey(sum - k)) {
                count += prefixSumMap.get(sum - k);
            }
            // 更新当前前缀和的出现次数
            prefixSumMap.put(sum, prefixSumMap.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

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

# 169. 多数元素 - 力扣（LeetCode） (opens new window)

# 摩尔投票

class Solution {
    public int majorityElement(int[] nums) {
        // 初始候选元素
        int candidate = nums[0];
        // 初始票数
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            // 票数归零时更新候选元素
            if (count == 0) { 
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                // 相同元素，票数增加
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
}

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 majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > nums.length / 2) {
                return num;
            }
        }
        return -1;
    }
}

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

编辑

上次更新: 2025/07/25, 12:08:10

← 排序排序→