无重复字符最长子串

  1. 输入: s = "abcabcbb"
  2. 输出: 3 
  3. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
  1. //匹配元素可能在最长无重复字符串中也可能没有。 即有可能会出现小于left边界的情况
  2. class Solution {
  3.     public int lengthOfLongestSubstring(String s) {
  4.         if(s.length() == 0) return 0;
  5.         if(s.length() == 1) return 1;
  6.         HashMap<Character, Integer> map = new HashMap();
  7.         int left = 0;
  8.         int max = 0;
  9.         for(int i = 0; i < s.length(); i++){
  10.             if(map.containsKey(s.charAt(i))){
  11.                 left = Math.max(left, map.get(s.charAt(i))+1);
  12.             }
  13.             map.put(s.charAt(i), i);
  14.             max = Math.max(max, i-left+1);
  15.         }
  16.         return max;
  17.     }
  18. }

盛水最多的容器

image.png

  1. 输入：[1,8,6,2,5,4,8,3,7]
  2. 输出：49 
  3. 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
  1. //双指针  容积为 左右最低高度*(右-左)
  2. class Solution {
  3.     public int maxArea(int[] height) {
  4.         int left = 0;
  5.         int right = height.length-1;
  6.         int res = 0;
  7.         int temp = 0;
  8.         while(left < right){
  9.             temp = height[left] > height[right] ?
  10.             (right-left)*height[right--]:
  11.             (right-left)*height[left++];
  12.             res = Math.max(res, temp);
  13.         }
  14.         return res;
  15.     }
  16. }

接雨水

image.png

  1. 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
  2. 输出：6
  3. 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
  1. class Solution {
  2. public int trap(int[] height) {
  3.     int left = 0, right = height.length - 1;
  4.     int ans = 0;
  5.     int left_max = 0, right_max = 0;
  6.     while (left < right) {
  7.         if (height[left] < height[right]) {
  8.             if (height[left] >= left_max) {
  9.                 left_max = height[left];
  10.             } else {
  11.                 ans += (left_max - height[left]);
  12.             }
  13.             ++left;
  14.         } else {
  15.             if (height[right] >= right_max) {
  16.                 right_max = height[right];
  17.             } else {
  18.                 ans += (right_max - height[right]);
  19.             }
  20.             --right;
  21.         }
  22.     }
  23.     return ans;
  24. }
  25. }

三数之和

  1. 输入：nums = [-1,0,1,2,-1,-4]
  2. 输出：[[-1,-1,2],[-1,0,1]]
  1. class Solution {
  2.     public List<List<Integer>> threeSum(int[] nums) {
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> res = new ArrayList();
  5.         for (int k = 0; k < nums.length - 2; k++) {
  6.             if(nums[k] > 0) break;
  7.             if(k > 0 && nums[k] == nums[k - 1]) continue;
  8.             int i = k + 1;
  9.             int j = nums.length - 1;
  10.             while(i < j) {
  11.                 int sum = nums[k] + nums[i] + nums[j];
  12.                 if(sum < 0) {
  13.                     while(i < j && nums[i] == nums[++i]);
  14.                 } else if(sum > 0) {
  15.                     while(i < j && nums[j] == nums[--j]);
  16.                 } else {
  17.                     res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
  18.                     while(i < j && nums[i] == nums[++i]);
  19.                     while(i < j && nums[j] == nums[--j]);
  20.                 }
  21.             } 
  22.         }
  23.         return res;
  24.     }
  25. }

合并两个有序数组

  1. 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
  2. 输出：[1,2,2,3,5,6]
  3. 解释：需要合并 [1,2,3] 和 [2,5,6] 。
  4. 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
  1. class Solution {
  2.     public void merge(int[] nums1, int m, int[] nums2, int n) {
  3.         int i = m - 1;
  4.         int j = n - 1;
  5.         int end = m + n - 1;
  6.         while (j >= 0) {
  7.             nums1[end--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];
  8.         }
  9.     }
  10. }

颜色分类