数组与字符串

数组基础

数组的特点？

答案：

• 连续内存空间
• 随机访问O(1)
• 插入删除O(n)
• 固定大小

常见操作

// 初始化
int[] arr = new int[5];
int[] arr2 = {1, 2, 3, 4, 5};

// 访问
int value = arr[0];

// 遍历
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

// 增强for
for (int num : arr) {
    System.out.println(num);
}

双指针技巧

两数之和（LeetCode 1）

答案：

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

三数之和（LeetCode 15）

答案：

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(nums);

    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;

        int left = i + 1, right = nums.length - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    return result;
}

盛最多水的容器（LeetCode 11）

答案：

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int maxArea = 0;

    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        maxArea = Math.max(maxArea, area);

        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

字符串

反转字符串（LeetCode 344）

答案：

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

最长回文子串（LeetCode 5）

答案：

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;

    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);

        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

字符串转整数（LeetCode 8）

答案：

public int myAtoi(String s) {
    s = s.trim();
    if (s.isEmpty()) return 0;

    int sign = 1, index = 0;
    if (s.charAt(0) == '+' || s.charAt(0) == '-') {
        sign = s.charAt(0) == '+' ? 1 : -1;
        index++;
    }

    long result = 0;
    while (index < s.length() && Character.isDigit(s.charAt(index))) {
        result = result * 10 + (s.charAt(index) - '0');
        if (result * sign > Integer.MAX_VALUE) return Integer.MAX_VALUE;
        if (result * sign < Integer.MIN_VALUE) return Integer.MIN_VALUE;
        index++;
    }
    return (int) (result * sign);
}

练习题

1. 删除排序数组中的重复项（LeetCode 26）
2. 移动零（LeetCode 283）
3. 验证回文串（LeetCode 125）
4. 最长公共前缀（LeetCode 14）
5. 字符串相乘（LeetCode 43）