1. 两数之和

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int[] ints = new int[2];
  5.         for (int i = 0; i < nums.length; i++) {
  6.             for (int j = i + 1; j < nums.length; j++) {
  7.                 if (target == nums[i] + nums[j]) {
  8.                     ints[0] = i;
  9.                     ints[1] = j;
  10.                     return ints;
  11.                 }
  12.             }
  13.         }
  14.         return ints;
  15.     }
  16. }
  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int[] ints = new int[2];
  6.         HashMap<Integer, Integer> hashMap = new HashMap<>();
  8.         hashMap.put(nums[0], 0);
  9.         for (int i = 1; i < nums.length; i++) {
  10.             Integer value = hashMap.get(target - nums[i]);
  11.             if (value != null) {
  12.                 ints[0] = i;
  13.                 ints[1] = value;
  14.                 return ints;
  15.             }
  16.             hashMap.put(nums[i], i);
  17.         }
  18.         return ints;
  19.     }
  20. }

2. 两数相加

  1. class Solution {
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  4.         ListNode cur1 = l1;
  5.         ListNode cur2 = l2;
  7.         // 虚拟头节点
  8.         ListNode dummy = new ListNode();
  9.         ListNode current = dummy;
  11.         // 用来表示进位
  12.         int carry = 0;
  14.         while (cur1 != null || cur2 != null) {
  16.             int val1 = (cur1 == null) ? 0 : cur1.val;
  17.             int val2 = (cur2 == null) ? 0 : cur2.val;
  18.             int sum = val1 + val2 + carry;
  20.             current.next = new ListNode(sum % 10);
  21.             current = current.next;
  23.             carry = sum / 10;
  25.             if (cur1 != null) {
  26.                 cur1 = cur1.next;
  27.             }
  28.             if (cur2 != null) {
  29.                 cur2 = cur2.next;
  30.             }
  31.         }
  32.         if (carry != 0) {
  33.             current.next = new ListNode(carry);
  34.         }
  36.         return dummy.next;
  37.     }
  38. }

3. 无重复字符的最长子串

窗口内是什么：无重复字符的字串
如何移动窗口的起始位置：当窗口 [i, j] 右边界的下一个字符存在窗口内，则窗口的起始位置变为 重复字符的下一个索引
如何移动窗口的结束位置：当窗口 [i, j] 右边界的下一个字符不存在窗口内，则窗口的结束位置 j + 1

  1. class Solution {
  3.     String s;
  5.     public int lengthOfLongestSubstring(String s) {
  6.         this.s = s;
  8.         // 定义窗口的边界
  9.         int winStart = 0;
  10.         int winEnd = 0;
  12.         // 定义一组和窗口有关的状态
  13.         int result = 0;
  15.         while (winEnd < s.length()) {
  16.             // 判断下标位置 winEnd 的字符是否重复出现在窗口 [winStart, winEnd] 内
  17.             int index = judge(winStart, winEnd);
  18.             if (index != -1) {
  19.                 winStart = index + 1;
  20.             } else {
  21.                 result = Math.max(result, winEnd - winStart + 1);
  22.                 winEnd++;
  23.             }
  24.         }
  25.         return result;
  26.     }
  28.     // 这个判断的逻辑可以用哈希表优化到 O(1) 
  29.     // 判断下标位置 winEnd 的字符是否重复出现在窗口 [winStart, winEnd] 内
  30.     // 如果没有重复出现，返回 -1；如果有重复出现，返回重复出现的下标
  31.     private int judge(int winStart, int winEnd) {
  32.         for (int i = winStart; i < winEnd; i++) {
  33.             if (s.charAt(i) == s.charAt(winEnd)) {
  34.                 return i;
  35.             }
  36.         }
  37.         return -1;
  38.     }
  39. }
  1. class Solution {
  3.     String s;
  5.     public int lengthOfLongestSubstring(String s) {
  6.         this.s = s;
  8.         // 定义窗口的边界
  9.         int winStart = 0;
  10.         int winEnd = 0;
  12.         // 定义一组和窗口有关的状态
  13.         int result = 0;
  14.         // key 为字符，value 为字符对于的下标
  15.         HashMap charMap = new HashMap();
  17.         while (winEnd < s.length()) {
  18.             // 判断下标位置 winEnd 的字符是否重复出现在窗口 [winStart, winEnd] 内
  19.             Integer value = (Integer) charMap.get(s.charAt(winEnd));
  21.             if (value == null) {
  22.                 charMap.put(s.charAt(winEnd), winEnd);
  23.                 result = Math.max(result, winEnd - winStart + 1);
  24.                 winEnd++;
  25.             } else {
  26.                 for (int i = winStart; i <= value; i++) {
  27.                     charMap.remove(s.charAt(i));
  28.                 }
  29.                 winStart = value + 1;
  30.             }
  31.         }
  32.         return result;
  33.     }
  34. }
class Solution {

    String s;

    public int lengthOfLongestSubstring(String s) {
        this.s = s;

        // 定义窗口的边界
        int winStart = 0;
        int winEnd = 0;

        // 定义一组和窗口有关的状态
        int result = 0;
        // key 为字符，value 为字符对于的下标
        HashMap charMap = new HashMap();

        while (winEnd < s.length()) {
            // 判断下标位置 winEnd 的字符是否重复出现在窗口 [winStart, winEnd] 内
            Integer value = (Integer) charMap.get(s.charAt(winEnd));

            if (value == null) {
                charMap.put(s.charAt(winEnd), winEnd);
                result = Math.max(result, winEnd - winStart + 1);
                winEnd++;
            } else {
                // 对上一个版本优化的地方(没有了 HashMap 移除的逻辑，时间复杂度更低)
                /*
                核心思想：
                    不移除新旧 winStart 之间的元素。若遍历出重复字符，则判断它的位置
                    若重复字符出现在 winStart 之前，说明该重复字符不在窗口内，窗口无需移动
                    若重复字符出现在 winStart 之后，说明该重复字符在窗口内，窗口需要移动
                 */
                winStart = Math.max(value + 1, winStart);
            }
        }
        return result;
    }
}

4. 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0) {
            if (nums2.length % 2 == 0) {
                double average = (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0;
                return average;
            } else {
                return nums2[nums2.length / 2];
            }
        }
        if (nums2.length == 0) {
            if (nums1.length % 2 == 0) {
                double average = (nums1[nums1.length / 2 - 1] + nums1[nums1.length / 2]) / 2.0;
                return average;
            } else {
                return nums1[nums1.length / 2];
            }
        }

        // 将两数组合并为一个有序数组
        int sum = nums1.length + nums2.length;
        int[] nums = new int[sum];
        int a1 = 0;
        int a2 = 0;
        int temp = 0;

        while (a1 < nums1.length && a2 < nums2.length) {
            if (nums1[a1] <= nums2[a2]) {
                nums[temp++] = nums1[a1++];
            } else {
                nums[temp++] = nums2[a2++];
            }
        }

        while (a1 < nums1.length) {
            nums[temp++] = nums1[a1++];
        }

        while (a2 < nums2.length) {
            nums[temp++] = nums2[a2++];
        }

        if (nums.length % 2 == 0) {
            double average = (nums[nums.length / 2 - 1] + nums[nums.length / 2]) / 2.0;
            return average;
        } else {
            return nums[nums.length / 2];
        }
    }
}

该题没有达到最小时间复杂度。

5.最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        int startIndex = 0;
        int endIndex = 0;

        for (int i = 0; i < s.length(); i++) {
            int length1 = expandAroundCenter(s, i, i);
            int length2 = expandAroundCenter(s, i, i + 1);
            int maxLength = Math.max(length1, length2);
            if (maxLength > (endIndex - startIndex + 1)) {
                startIndex = i - (maxLength - 1) / 2;
                endIndex = i + maxLength / 2;
            }
        }
        return s.substring(startIndex, endIndex + 1);
    }

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

        return rTemp - lTemp - 1;
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int startIndex = 0;
        int endIndex = 0;

        // dp[i][j]的含义：用 dp[i][j] 的值来标记下标i到下标j构成的子字符串是否为回文串，是回文串值为 1，不是值为 0
        boolean[][] dp = new boolean[s.length()][s.length()];

        // 确定递推方程 dp[i][j] = dp[i + 1][j - 1] && (s.charAt(i) == s.charAt(j))

        // dp 数组初始化
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }

        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                // 处理特殊情况
                dp[i][j] = (j - i < 2 || dp[i + 1][j - 1]) && (s.charAt(i) == s.charAt(j));

                if (dp[i][j] && j - i + 1 > endIndex - startIndex + 1) {
                    startIndex = i;
                    endIndex = j;
                }
            }

        }
        return s.substring(startIndex, endIndex + 1);
    }
}

7. 整数反转

class Solution {
    public int reverse(int x) {
        int result = 0;

        while (x != 0) {
            if (result > Integer.MAX_VALUE / 10 || result < Integer.MIN_VALUE / 10) {
                return 0;
            }
            int num = x % 10;
            result = result * 10 + num;
            x /= 10;
        }
        return result;
    }
}

8. 字符串转换整数 (atoi)

10. 正则表达式匹配

11. 盛最多水的容器

13. 罗马数字转整数

14. 最长公共前缀

15. 三数之和

17. 电话号码的字母组合

19. 删除链表的倒数第 N 个结点

20. 有效的括号

21. 合并两个有序链表

22. 括号生成

23. 合并K个升序链表

26. 删除有序数组中的重复项

28. 实现 strStr()

29. 两数相除

33. 搜索旋转排序数组

34. 在排序数组中查找元素的第一个和最后一个位置

36. 有效的数独

38. 外观数列

41. 缺失的第一个正数

42. 接雨水

44. 通配符匹配

46. 全排列

48. 旋转图像

49. 字母异位词分组

50. Pow(x, n)

53. 最大子数组和

54. 螺旋矩阵

55. 跳跃游戏

56. 合并区间

62. 不同路径

66. 加一

69. x 的平方根

70. 爬楼梯

73. 矩阵置零

75. 颜色分类

76. 最小覆盖子串

78. 子集

79. 单词搜索

84. 柱状图中最大的矩形

88. 合并两个有序数组

91. 解码方法

94. 二叉树的中序遍历

98. 验证二叉搜索树