引言

数组和字符串是算法题的基础。本文精选经典题目和解法。

一、双指针

1.1 两数之和II（LeetCode 167）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 + 1, right + 1};
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return new int[]{};
}

1.2 反转字符串（LeetCode 344）

1
2
3
4
5
6
7
8
9
10
11
public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

二、滑动窗口

2.1 最长无重复子串（LeetCode 3）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int maxLen = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        while (set.contains(s.charAt(right))) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(s.charAt(right));
        maxLen = Math.max(maxLen, right - left + 1);
    }
    
    return maxLen;
}

三、前缀和

3.1 子数组和等于K（LeetCode 560）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    
    int sum = 0, count = 0;
    for (int num : nums) {
        sum += num;
        if (map.containsKey(sum - k)) {
            count += map.get(sum - k);
        }
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }
    
    return count;
}

总结

数组字符串核心技巧：

  1. 双指针：相向、同向指针
  2. 滑动窗口：动态窗口大小
  3. 前缀和：快速求区间和

参考资料