1. 两数之和 题目描述 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
1 2 3 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
1 2 输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
1 2 输入：nums = [3,3], target = 6 输出：[0,1]
题解 1. 暴力 两次枚举，需要两次遍历，时间复杂度O(n²)
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution { public int [] twoSum(int [] nums, int target) { for (int i = 0 ; i < n; i++) { for (int j = i + 1 ; j < nums.length; j++) { if (nums[i] + nums[j] == target) { return new int []{i, j}; } } } } }
ACM模式：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 import java.util.Scanner;public class Main { public static void main (String[] args) { Scanner scanner = new Scanner (System.in); int n = scanner.nextInt(); int target = scanner.nextInt(); int [] nums = new int [n]; for (int i = 0 ; i < n; i++) { nums[i] = scanner.nextInt(); } for (int i = 0 ; i < n; i++) { for (int j = i + 1 ; j < n; j++) { if (nums[i] + nums[j] == target) { System.out.println(i + " " + j); return ; } } } } }
2. 双指针 由于题目所给数组已经有序 排列，则可以从两端开始取数，如果两端取数的和大于目标，则说明：和为目标值的两个元素一定在两端范围内，时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int [] twoSum(int [] nums, int target) { int left = 0 ; int right = nums.length - 1 ; while (true ) { if ((nums[right] + nums[left]) > target){ right--; } else if ((nums[right] + nums[left]) < target){ left++; } else { return new int []{left, right}; } } } }
3. HashMap 使用HashMap的key作为元素值，value作为数组下标
把元素存到HashMap中，去查找HashMap中与元素相加等于target的key
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import java.util.HashMap;class Solution { public int [] twoSum(int [] nums, int target) { HashMap<Integer, Integer> map = new HashMap <>(); for (int i = 0 ; i < nums.length; i++){ int need = target - nums[i]; if (map.containsKey(need)){ return new int []{map.get(need), i}; } map.put(nums[i], i); } return new int []{-1 ,-1 }; } }
心得 很多涉及到「两个变量」的题目，都可以枚举其中一个变量，把它当成常量 看待，从而转化成「一个变量」的问题。
代码实现时，通常来说「枚举右，寻找左」是更加好写的。
2. 统计和小于目标的下标对数目 题目描述 给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的下标对 (i, j) 的数目。
示例 1：
1 2 3 4 5 6 7 输入：nums = [-1,1,2,3,1], target = 2 输出：3 解释：总共有 3 个下标对满足题目描述： - (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target - (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target - (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target 注意 (0, 3) 不计入答案因为 nums[0] + nums[3] 不是严格小于 target 。
示例 2：
1 2 3 4 5 6 7 8 9 10 11 12 13 输入：nums = [-6,2,5,-2,-7,-1,3], target = -2 输出：10 解释：总共有 10 个下标对满足题目描述： - (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target - (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target - (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target - (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target - (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target - (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target - (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target - (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target - (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target - (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target
题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { public int countPairs (List<Integer> nums, int target) { Collections.sort(nums); int n = nums.size(); int num = 0 ; for (int i = 0 ; i < n; i++) { int x = nums.get(i); int j = n - 1 ; while (j > i) { if (nums.get(j) + x < target){ j--; num++; } else break ; } } return num; } }
要点 List不能通过[]下标访问元素，通过list.get(i)获取元素，list.set(i, x) 设置元素，list.size()获取长度
3. 三数之和 题目描述 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
**注意：**答案中不可以包含重复的三元组。
示例 1：
1 2 3 4 5 6 7 8 输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]] 解释： nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
1 2 3 输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
1 2 3 输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
题解
输出的顺序和三元组的顺序并不重要。则可以规定 i < j < k
答案中不可以包含重复的三元组。只需要跳过重复的枚举数(确保三个数字中必有一个不同)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { public List<List<Integer>> threeSum (int [] nums) { Arrays.sort(nums); int n = nums.length; List<List<Integer>> list = new ArrayList (); for (int i = 0 ; i < nums.length-2 ; i++){ if (i > 0 && nums[i] == nums[i-1 ]) { continue ; } if ((nums[i] + nums[i+1 ] + nums[i+2 ]) > 0 ) { break ; } if ((nums[i] + nums[n-1 ] + nums[n-2 ]) < 0 ) { continue ; } int j = i + 1 ; int k = n - 1 ; while (j < k) { int s = nums[i] + nums[j] + nums[k]; if (s > 0 ) { k--; } else if (s < 0 ) { j++; } else { list.add(Arrays.asList(nums[i], nums[j], nums[k])); j++; while (j < k && nums[j] == nums[j-1 ]) { j++; } k--; while (k > j && nums[k] == nums[k+1 ]) { k--; } } } } return list; } }
思路
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
4. 最接近的三数之和 题目描述 给定一个长度为 n 的整数数组 nums 和 一个整数 target。
请你从 nums 中选出三个在 不同下标位置 的整数，使它们的和与 target 最接近 。
返回这三个数的和。
假定每组输入只存在 恰好 一个解。
示例 1：
1 2 3 输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：
1 2 3 输入：nums = [0,0,0], target = 1 输出：0 解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public int threeSumClosest (int [] nums, int target) { Arrays.sort(nums); int n = nums.length; int ans = Integer.MAX_VALUE / 2 ; for (int i = 0 ; i < n-2 ; i++) { int x = nums[i]; if (i > 0 && x == nums[i - 1 ]) { continue ; } int s = x + nums[i + 1 ] + nums[i + 2 ]; if (s > target) { if (s - target < Math.abs(ans - target)) { ans = s; } break ; } s = x + nums[n - 2 ] + nums[n - 1 ]; if (s < target) { if (target - s < Math.abs(ans - target)) { ans = s; } continue ; } int j = i + 1 ; int k = n - 1 ; while (j < k) { s = x + nums[j] + nums[k]; if (s == target) { return target; } if (Math.abs(s - target) < Math.abs(ans - target)) { ans = s; } if (s > target) { k --; } else { j++; } } } return ans; } }
5. 四数之和 题目描述 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复 的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c 和 d 互不相同 nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
1 2 输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
1 2 输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public List<List<Integer>> fourSum (int [] nums, int target) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList <>(); int n = nums.length; for (int a = 0 ; a < n - 3 ; a++) { long x = nums[a]; if (a > 0 && x == nums[a - 1 ]) continue ; if (x + nums[a + 1 ] + nums[a + 2 ] + nums[a + 3 ] > target) break ; if (x + nums[n - 3 ] + nums[n - 2 ] + nums[n - 1 ] < target) continue ; for (int b = a + 1 ; b < n - 2 ; b++) { long y = nums[b]; if (b > a + 1 && y == nums[b - 1 ]) continue ; if (x + y + nums[b + 1 ] + nums[b + 2 ] > target) break ; if (x + y + nums[n - 2 ] + nums[n - 1 ] < target) continue ; int c = b + 1 ; int d = n - 1 ; while (c < d) { long s = x + y + nums[c] + nums[d]; if (s > target) d--; else if (s < target) c++; else { ans.add(List.of((int )x, (int )y, nums[c], nums[d])); for (c++; c < d && nums[c] == nums[c - 1 ]; c++); for (d--; d > c && nums[d] == nums[d + 1 ]; d--); } } } } return ans; } }
6. 有效三角形的个数 题目描述 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
1 2 3 4 5 6 输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3
示例 2:
1 2 输入: nums = [4,2,3,4] 输出: 4
错解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public int triangleNumber (int [] nums) { Arrays.sort(nums); int n = nums.length; int ans = 0 ; for (int a = 0 ; a < n-2 ; a++) { int b = a + 1 ; int c = n - 1 ; while (b < c) { if (nums[c] - nums[a] < nums[b]) { ans += c - b; b++; } else { c--; } } } return ans; } }
错解原因：nums[c] - nums[a] < nums[b] 则说明两小边必大于大边
题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int triangleNumber (int [] nums) { Arrays.sort(nums); int n = nums.length; int ans = 0 ; for (int c = n - 1 ; c > 1 ; c--) { int a = 0 ; int b = c - 1 ; while (b > a) { if (nums[a] + nums[b] > nums[c]) { ans += b - a; b--; } else { a++; } } } return ans; } }
优化：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int triangleNumber (int [] nums) { Arrays.sort(nums); int ans = 0 ; for (int k = nums.length - 1 ; k > 1 ; k--) { int c = nums[k]; if (nums[0 ] + nums[1 ] > c) { ans += (k + 1 ) * k * (k - 1 ) / 6 ; break ; } if (nums[k - 2 ] + nums[k - 1 ] <= c) { continue ; } int i = 0 ; int j = k - 1 ; while (i < j) { if (nums[i] + nums[j] > c) { ans += j - i; j--; } else { i++; } } } return ans; } }
7. 盛水最多的容器 题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
**说明：**你不能倾斜容器。
示例 1：
1 2 3 输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
题解 错误解法：暴力 时间复杂度O(n²)
1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public int maxArea (int [] height) { int n = height.length; int ans = 0 ; for (int l = 0 ; l < n; l++) { for (int r = n - 1 ; r > l; r--){ ans = Math.max(ans, (r - l) * Math.min(height[l], height[r])); } } return ans; } }
正确解法：双指针 移动height较小的边 (因为若想扩大面积，移动双指针长度必定减小，则必须使高度增加，则优先移动小边) 时间复杂度O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int maxArea (int [] height) { int n = height.length; int left = 0 ; int right = n - 1 ; int ans = 0 ; while (left < right) { int h = Math.min(height[left], height[right]); int area = h * (right - left); ans = Math.max(ans, area); if (height[left] < height[right]) { left++; } else { right--; } } return ans; } }
优化思路：移动指针后可以进行一个高度判断：如果高度比原位置低，则不用计算面积
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int maxArea (int [] height) { int left = 0 ; int right = height.length - 1 ; int ans = 0 ; while (left < right) { int leftHeight = height[left]; int rightHeight = height[right]; int area = (right - left) * Math.min(leftHeight, rightHeight); ans = Math.max(ans, area); if (leftHeight < rightHeight) { while (left < right && height[left] <= leftHeight) { left++; } } else { while (left < right && height[right] <= rightHeight) { right--; } } } return ans; } }
8. 接雨水 题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：
1 2 3 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
1 2 3 输入：height = [4,2,0,3,2,5] 输出：9
题解
计算每一块能接的雨水量：左右两边记录高度的最小值 - 当前高度
记录：高度更新的最大值
如果当前高度大于记录高度的最小值，则更新记录高度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int trap (int [] height) { int n = height.length; int ans = 0 ; int left = 0 ; int right = n - 1 ; int pre_max = 0 ; int suf_max = 0 ; while (left <= right) { pre_max = Math.max(pre_max, height[left]); suf_max = Math.max(suf_max, height[right]); if (pre_max < suf_max) { ans += pre_max - height[left]; left++; } else { ans += suf_max - height[right]; right--; } } return ans; } }
9. 验证回文串 题目描述 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例 1：
1 2 3 输入: s = "A man, a plan, a canal: Panama" 输出：true 解释："amanaplanacanalpanama" 是回文串。
示例 2：
1 2 3 输入：s = "race a car" 输出：false 解释："raceacar" 不是回文串。
示例 3：
1 2 3 4 输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。
题解 时间复杂度 O(n) ，空间复杂度 O(n) 。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public boolean isPalindrome (String s) { s = s.toLowerCase().replaceAll("[^a-z0-9]" , "" ); String[] arr = s.split("" ); int left = 0 ; int right = arr.length - 1 ; while (left <= right) { if (arr[left].equals(arr[right])) { left ++; right --; } else { return false ; } } return true ; } }
优化：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public boolean isPalindrome (String s) { int i = 0 ; int j = s.length() - 1 ; while (i < j) { if (!Character.isLetterOrDigit(s.charAt(i))) { i++; } else if (!Character.isLetterOrDigit(s.charAt(j))) { j--; } else if (Character.toLowerCase(s.charAt(i)) == Character.toLowerCase(s.charAt(j))) { i++; j--; } else { return false ; } } return true ; } }
要点 Character.isLetterOrDigit() 判断某个字符是不是”数字或字母”
Character.toLowerCase() 将字符转为小写
== 比较的是地址，比较值要用.euqals()
10. 给植物浇水II 题目描述 Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
无论需要多少水，为每株植物浇水所需的时间都是相同的。
如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先 （立即）重新装满罐子，然后给植物浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例 1：
1 2 3 4 5 6 7 8 输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5 输出：1 解释： - 最初，Alice 和 Bob 的水罐中各有 5 单元水。 - Alice 给植物 0 浇水，Bob 给植物 3 浇水。 - Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。 - Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。 所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
示例 2：
1 2 3 4 5 6 7 8 输入：plants = [2,2,3,3], capacityA = 3, capacityB = 4 输出：2 解释： - 最初，Alice 的水罐中有 3 单元水，Bob 的水罐中有 4 单元水。 - Alice 给植物 0 浇水，Bob 给植物 3 浇水。 - Alice 和 Bob 现在都只有 1 单元水，并分别需要给植物 1 和植物 2 浇水。 - 由于他们的水量均不足以浇水，所以他们重新灌满水罐再进行浇水。 所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 1 + 1 + 0 = 2 。
示例 3：
1 2 3 4 5 6 输入：plants = [5], capacityA = 10, capacityB = 8 输出：0 解释： - 只有一株植物 - Alice 的水罐有 10 单元水，Bob 的水罐有 8 单元水。因此 Alice 的水罐中水更多，她会给这株植物浇水。 所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 。
题解 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public int minimumRefill (int [] plants, int capacityA, int capacityB) { int n = plants.length; int count = 0 ; int left = 0 ; int right = n - 1 ; int A = capacityA; int B = capacityB; while (left < right) { if (B >= plants[right] && A >= plants[left]) { B -= plants[right]; A -= plants[left]; left++; right--; } else if (A < plants[left]) { A = capacityA; count ++; }else if (B < plants[right]) { B = capacityB; count++; } } if (left == right) { if (Math.max(A, B) < plants[left]) { count++; } } return count; } }
优化
while 一次操作即为AB两人浇一次水，不用if判断保证两人浇水次数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public int minimumRefill (int [] plants, int capacityA, int capacityB) { int ans = 0 ; int a = capacityA; int b = capacityB; int i = 0 ; int j = plants.length - 1 ; while (i < j) { if (a < plants[i]) { ans++; a = capacityA; } a -= plants[i++]; if (b < plants[j]) { ans++; b = capacityB; } b -= plants[j--]; } if (i == j && Math.max(a, b) < plants[i]) { ans++; } return ans; } }
相向双指针总结
