HOT100

哈希

P1 两数之和

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

P49 字母异位词分组

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String str : strs) {
        char[] cnt = new char[26];
        for (int i = 0; i < str.length(); i++) {
            cnt[str.charAt(i) - 'a']++;
        }
        String temp = new String(cnt);
        if (!map.containsKey(temp)) {
            map.put(temp, new ArrayList<>());
        }
        map.get(temp).add(str);
    }
    return new ArrayList<>(map.values());
}

P128 最长连续序列

解法一

• 使用 set 去重
• 遍历集合，如果元素是区间的第一个元素，即 set.contains(num - 1)，则循环获取区间长度
• 由于每个元素只会遍历一次，因此时间复杂度为 O(n)

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }

    int max = 0;
    for (int num : set) {
        if (!set.contains(num - 1)) {
            int currentNum = num;
            int count = 1;

            while (set.contains(currentNum + 1)) {
                currentNum += 1;
                count += 1;
            }

            max = Math.max(max, count);
        }
    }

    return max;
}

解法二：动态规划

public int longestConsecutive(int[] nums) {
    // 表示 key 包含在区间中的最长长度
    HashMap<Integer, Integer> map = new HashMap<>();
    int max = 0;
    for (int num : nums) {
        // 不存在哈希表中，说明num第一次出现，因此num-1必为右端点，num+1必为左端点
        if (!map.containsKey(num)) {
            Integer leftLen = map.getOrDefault(num - 1, 0);
            Integer rightLen = map.getOrDefault(num + 1, 0);

            int length = 1 + leftLen + rightLen;
            max = Math.max(length, max);

            map.put(num, length);
            map.put(num - leftLen, length);
            map.put(num + rightLen, length);
        }
    }

    return max;
}

双指针

P283 移动零

public void moveZeroes(int[] nums) {
    int left = 0;
    int right = 0;

    while (right < nums.length) {
        if (nums[right] != 0) {
            nums[left++] = nums[right++];
        } else {
            right++;
        }
    }
    while (left < nums.length) {
        nums[left++] = 0;
    }
}

P11 盛水最多的容器

public int maxArea(int[] height) {
    int left = 0, right = height.length - 1;
    int max = 0;
    while (left < right) {
        int area = Math.min(height[left], height[right]) * (right - left);
        max = Math.max(max, area);
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return max;
}

P15 三数之和

• 排序数组
• 固定 first，枚举 second，由于数组升序，当 second 不断增加，third 会不断减少，由于单调性，固定 first 时，second ~ n 每个元素只会遍历一次，因此时间复杂度为 O(n^2)
• 为了保证不重复，枚举的值需要与前一个值不同

public List<List<Integer>> threeSum(int[] nums) {
    int n = nums.length;
    Arrays.sort(nums);
    List<List<Integer>> ans = new ArrayList<>();
    // 枚举 a
    for (int first = 0; first < n; ++first) {
        // 需要和上一次枚举的数不相同
        if (first > 0 && nums[first] == nums[first - 1]) {
            continue;
        }
        // c 对应的指针初始指向数组的最右端
        int third = n - 1;
        int target = -nums[first];
        // 枚举 b
        for (int second = first + 1; second < n; ++second) {
            // 需要和上一次枚举的数不相同
            if (second > first + 1 && nums[second] == nums[second - 1]) {
                continue;
            }
            // 需要保证 b 的指针在 c 的指针的左侧
            while (second < third && nums[second] + nums[third] > target) {
                --third;
            }
            if (second == third) {
                break;
            }
            if (nums[second] + nums[third] == target) {
                List<Integer> list = new ArrayList<>();
                list.add(nums[first]);
                list.add(nums[second]);
                list.add(nums[third]);
                ans.add(list);
            }
        }
    }
    return ans;
}

P42 接雨水

public int trap(int[] height) {
    int n = height.length;
    int left = 0, right = n - 1;
    int leftMax = height[left], rightMax = height[right];
    left++;
    right--;
    int sum = 0;
    // 计算每一列能存储的雨水相加
    while (left <= right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (leftMax < rightMax) {
            sum += leftMax - height[left++];
        } else {
            sum += rightMax - height[right--];
        }
    }
    return sum;
}

滑动窗口

P3 无重复字符的最长子串

public int lengthOfLongestSubstring(String s) {
    int[] cnt = new int[258];
    int ans = 0;
    int left = 0, right = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        cnt[c]++;
        if (cnt[c] > 1) {
            ans = Math.max(right - left, ans);
            while (cnt[c] > 1) {
                cnt[s.charAt(left++)]--;
            }
        }
        right++;
    }
    ans = Math.max(right - left, ans);
    return ans;
}

P438 找到字符串中所有字母异位词

public List<Integer> findAnagrams(String s, String p) {
    if(s.length() < p.length()) return new ArrayList<>();
    int[] cnt = new int[26];
    for (char c : p.toCharArray()) {
        cnt[c - 'a']++;
    }
    int[] counts = new int[26];

    int left = 0, right = p.length();
    for (int i = 0; i < p.length(); i++) {
        counts[s.charAt(i) - 'a']++;
    }
    List<Integer> ans = new ArrayList<>();
    while (right < s.length()) {
        if (Arrays.equals(counts, cnt)) {
            ans.add(left);
        }
        counts[s.charAt(left++) - 'a']--;
        counts[s.charAt(right++) - 'a']++;
    }
    if(Arrays.equals(counts, cnt)) ans.add(left);
    return ans;
}

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();

    int[] need = new int[26];
    int[] windows = new int[26];
    int needNum = 0;

    for (int i = 0; i < p.length(); i++) {
        int idx = p.charAt(i) - 'a';
        if (need[idx] == 0)
            needNum++;
        need[idx]++;
    }
    // aabaa  ab
    int count = 0;
    int left = 0, right = 0;

    while (right < s.length()) {
        int idx_r = s.charAt(right) - 'a';
        windows[idx_r]++;
        if (need[idx_r] == windows[idx_r]) {
            count++;
        }
        while (right - left + 1 >= p.length()) {
            if (count == needNum) {
                res.add(left);
            }
            int idx_l = s.charAt(left) - 'a';
            if (need[idx_l] == windows[idx_l]) {
                count--;
            }
            windows[idx_l]--;
            left++;
        }
        right++;
    }
    return res;
}

矩阵

P48 旋转图像

public void rotate(int[][] matrix) {
    int n = matrix.length;

    // 上下翻转
    for (int i = 0; i < n / 2; i++) {
        for (int j = 0; j < n; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[n - 1 -i][j];
            matrix[n - 1 -i][j] = tmp;
        }
    }

    // 左斜对角线(\)翻转
    for(int i = 0; i < n; i++) {
        // 第二层遍历终止条件为 j < i
        for(int j = 0; j < i; j++) {
            int tmp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = tmp;
        }
    }
}

P240 搜索二维矩阵 II

public boolean searchMatrix(int[][] matrix, int target) {
    int n = matrix.length, m = matrix[0].length;
    int i = 0, j = matrix[0].length - 1;
    while (i < n && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            j--;
        } else if (matrix[i][j] < target) {
            i++;
        }
    }
    return false;
}

链表

P160 相交链表

pA 和 pB 遍历到末尾时重新遍历另一条链表以消除长度差

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA;
    ListNode pB = headB;
    while (pA != pB) {
        pA = pA == null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}

P234 回文链表

• 慢指针反转前半段链表
• 遍历前半段和后半段链表是否一致

public boolean isPalindrome(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    ListNode pre = null;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        ListNode next = slow.next;
        slow.next = pre;
        pre = slow;
        slow = next;
    }
    // 奇数节点
    if (fast != null) {
        slow = slow.next;
    }
    while (slow != null) {
        if (slow.val != pre.val) return false;
        slow = slow.next;
        pre = pre.next;
    }
    return true;
}

P141 环形链表

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}