LeetCode

1. 两数之和 经典题

如果是直接返回数本身，可以先排序，然后再用双指针来做。
但题目要求返回的是序号，所以用map来存储每个数的下标，时间复杂度为O(n)，空间复杂度为O(n)。

  2. public int[] twoSum(int[] nums, int target) {
  3.     if (nums == null)   return null;
  4.     Map<Integer, Integer> count = new HashMap();
  5.     for (int i = 0; i < nums.length; i++) {
  6.         if (count.get(target - nums[i]) != null) {
  7.             return new int[] {count.get(target - nums[i]), i};
  8.         }
  9.         count.put(nums[i], i);
  10.     }
  11.     return null;
  12. }

18. 四数之和

首先想到的DFS，考虑到超时问题，一般需要剪枝处理。
先排好序，分三种情况，第一种是剩下的元素已经不足4个；第二种是剩下元素一定比target大，第三种是剩下元素一定比target小。

  1. List<List<Integer>> res = new ArrayList();
  2. public List<List<Integer>> fourSum(int[] nums, int target) {
  3.     if (nums == null)   return null;
  4.     Arrays.sort(nums);
  5.     fourSum(nums, target, new ArrayList<Integer>(), 0);
  6.     return res;
  7. }
  8. public void fourSum(int[] nums, int target, List<Integer> curList, int curIdx) {
  9.     if (curList.size() == 4) {
  10.         if (target == 0) {
  11.             res.add(new ArrayList<Integer>(curList));
  12.         }
  13.         return ;
  14.     }
  15.     //剪枝
  16.     if (nums.length - curIdx + 1 + curList.size() < 4)  return ;
  17.     if (curIdx < nums.length && (4 - curList.size()) * nums[curIdx] > target)   return ;
  18.     if ((4 - curList.size()) * nums[nums.length-1] < target)    return ;
  20.     Set<Integer> set = new HashSet();
  21.     for (int i = curIdx; i < nums.length; i++) {
  22.         if (set.contains(nums[i]))  continue;
  23.         set.add(nums[i]);
  24.         curList.add(nums[i]);
  25.         fourSum(nums, target-nums[i], curList, i+1);
  26.         curList.remove(curList.size()-1);
  27.     }
  28. }

官方答案思路：暴力四重循环优化，先使用两重循环枚举前两个数，然后在两重循环枚举到的数之后使用双指针枚举剩下的两个数。时间复杂度为O(n)，空间复杂度为O(n)（排序可能需要额外数组）。
去重和剪枝的代码稍微麻烦点，容易出错，不建议写这种。

  1. public List<List<Integer>> fourSum(int[] nums, int target) {
  2.     List<List<Integer>> res = new ArrayList();
  3.     if (nums == null)   return null;
  4.     Arrays.sort(nums);
  5.     int length = nums.length;
  6.     //第一重循环
  7.     for (int i = 0; i < length - 3; i++) {
  8.         //去重
  9.         if (i > 0 && nums[i] == nums[i-1])  continue;
  10.         //剪枝处理
  11.         if (nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target)   break;
  12.         if (nums[i] + nums[length-3] + nums[length-2] + nums[length-1] < target)    continue;
  13.         //第二重循环
  14.         for (int j = i+1; j < length - 2; j++) {
  15.             //去重
  16.             if (j > i + 1 && nums[j] == nums[j-1])  continue;
  17.             //剪枝处理
  18.             if (nums[i] + nums[j] + nums[j+1] + nums[j+2] > target)   break;
  19.             if (nums[i] + nums[j] + nums[length-2] + nums[length-1] < target)    continue;
  20.             //双指针
  21.             int left = j + 1,  right = length-1;
  22.             while (left < right) {
  23.                 int sum = nums[i] + nums[j] + nums[left] + nums[right];
  24.                 if (sum == target) {
  25.                     res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
  26.                     while (left < right && nums[left] == nums[left+1]) {
  27.                         left++;
  28.                     }
  29.                     left++;
  30.                 } else if (sum < target) {
  31.                     left++;
  32.                 } else if (sum > target) {
  33.                     right--;
  34.                 }
  35.             }
  36.         }
  37.     }
  38.     return res;
  39. }

57. 和为s的两个数字（剑指 Offer ）

题目已经排好序了，直接套模板就行。

  1. public int[] twoSum(int[] nums, int target) {
  2.     if (nums == null)   return null;
  3.     int l = 0, r = nums.length-1;
  4.     while (l < r) {
  5.         int sum = nums[l] + nums[r];
  6.         if (sum == target)  break;
  7.         else if (sum < target)  l++;
  8.         else if (sum > target)  r--;
  9.     }
  10.     return l == r ? null : (new int[] {nums[l], nums[r]});
  11. }

75. 颜色分类

将数组排列成红蓝白的顺序，假设0代表红，1代表蓝，2代表白。
比较容易想到的解法是计数排序，先一遍扫描出0，1，2的个数，然后在更改，但这样需要两遍扫描
现在要求只扫描一遍，且使用常数空间。
解法一：两个指针pt0，pt1分别指向已经排好序0的位置和1的位置（注意初始值都设为-1，因此是++pt）。根据当前遍历的值，可以分三种情况：
（1）如果当前值是0；这里比较特殊了。
如果pt0==pt1，意味着到现在为止还没有做过值是1的处理，交换指针i和指针pt0的值，一定是交换值2和0。因此，不仅需要移动pt0，而且还要移动pt1。此时由于nums[i] == 2，相当于不会走后面的语句了。
如果pt0<pt1，那么交换指针i和指针pt0的值，一定是交换值1和0。因此，不能直接i++继续遍历，而是还要继续走第2种情况，这就是为什么不写else if，而是直接写if。
（2）如果当前值是1；交换指针i和指针pt1的值，一定是交换值2和1。
（3）如果当前值是2；不需要做任何处理，只需要继续向后遍历，即i++。

  1. public void sortColors(int[] nums) {
  2.     if (nums == null)   return ;
  3.     int pt0 = -1, pt1 = -1;
  4.     for (int i = 0; i < nums.length; i++) {
  5.         if (nums[i] == 0) {
  6.             if (pt0 == pt1) pt1++;
  7.             swap(nums, ++pt0, i);
  8.         }
  9.         if (nums[i] == 1) {
  10.             swap(nums, ++pt1, i);
  11.         }
  12.     }
  13. }
  14. public void swap(int[] nums, int i, int j) {
  15.     int temp = nums[i];
  16.     nums[i] = nums[j];
  17.     nums[j] = temp;
  18. }

解法二：两个指针指向的是排好序0和2的位置，0放到最前面，2放到最后面。简单认为，pt0之前的都为0，pt2之后的都为2。

  1. public void sortColors(int[] nums) {
  2.     if (nums == null)   return ;
  3.     int pt0 = -1, pt2 = nums.length;
  4.     for (int i = 0; i < pt2;i++) {
  5.         while (i < pt2 && nums[i] == 2) {
  6.             swap(nums, --pt2, i);
  7.         }
  8.         if (nums[i] == 0) {
  9.             swap(nums, ++pt0, i);
  10.         }
  12.     }
  13. }

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。

  1. public List<Integer> partitionLabels(String S) {
  2.     List<Integer> res = new ArrayList();
  3.     int[] lastIndex  = new int[26];
  4.     for (int i = 0; i < S.length(); i++) {
  5.         lastIndex[S.charAt(i)-'a'] = i;
  6.     }
  7.     int start = 0, end = 0;
  8.     for (int i = 0; i < S.length(); i++) {
  9.         int ch = S.charAt(i) - 'a';
  10.         end = Math.max(end, lastIndex[ch]);
  11.         if (end == i) {
  12.             res.add(end - start + 1);
  13.             start = ++end;
  14.         }
  15.     }
  16.     return res;
  17. }

贪心+双指针：从左到右遍历字符串，同时维护当前片段的开始下标start和结束下标end，对于访问到的当前字符，如果字符的最后下标大于end，那么需要延长当前片段的结束下标end。
时间复杂度为O(n)，空间复杂度为O(Σ)，其中Σ=26。

925. 长按键入

  1. public boolean isLongPressedName(String name, String typed) {
  2.     if (name == null || typed == null)  return true;
  3.     int i = 0, j = 0;
  4.     // char lastChar1 = name.charAt(i), lastChar2 = type.charAt(j);
  5.     while (j < typed.length()) {
  6.         if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
  7.             i++;    j++;
  8.         } else if (j > 0 && typed.charAt(j-1) == typed.charAt(j)) {
  9.             j++;
  10.         } else {
  11.             return false;
  12.         }
  13.     }
  14.     return i == name.length() && j == typed.length();
  15. }

这个题的边界容易出错，怎么写好这个循环还有点东西的。主要是找出正确的情况，其他情况全部返回false就行。

977. 有序数组的平方

非递减顺序排列的整数数组A，返回每个数字平方组成的新的非递减数组

一种解法是归并排序，先找到正负数的分界线，然后利用两边都是有序的性质，进行归并排序。
另一种解法是双指针，不需要判断越界等边界问题，代码更加优雅。

  1. public int[] sortedSquares(int[] A) {
  2.     if (A == null)  return A;
  3.     int n = A.length;
  4.     int[] res = new int[n];
  6.     int i = 0;
  7.     for (; i < n; i++) {
  8.         if (A[i] >= 0)   break;
  9.         res[n - i -1] = A[i] * A[i];
  10.     }
  11.     int i1 = n-i, i2 = i;
  12.     for (int j = 0; j < n; j++) {
  13.         if (i1 == n) {
  14.             res[j] = A[i2] * A[i2++];
  15.             continue;
  16.         }
  17.         if (i2 == n)    break;
  18.         res[j] = res[i1] < A[i2]*A[i2] ? res[i1++] : A[i2]*A[i2++];
  19.     }
  20.     return res;
  21. }
  22. public int[] sortedSquares(int[] A) {
  23.     if (A == null)  return A;
  24.     int n = A.length;
  25.     int[] res = new int[n];
  26.     int i1 = 0, i2 = n-1;
  27.     for (int j = n-1; j >= 0; j--) {
  28.         int v1 = A[i1] * A[i1];
  29.         int v2 = A[i2] * A[i2];
  30.         if (v1 > v2) {
  31.             res[j] = v1;
  32.             i1++;
  33.         } else {
  34.             res[j] = v2;
  35.             i2--;
  36.         }
  37.     }
  38.     return res;
  39. }

时间复杂度都为O(n)，空间复杂度都为O(n)。