原地修改数组（快慢指针）

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

问题描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例1

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例2

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

代码

static int removeDuplicates(int[] nums) {int slow = 0;int fast = 1;while (fast < nums.length) {if (nums[slow] != nums[fast]) {//slow先+1，给出位置，然后再赋值//维护 nums[0..slow] 无重复nums[++slow] = nums[fast];}fast++;}//数组长度为索引 + 1return slow + 1;
}

扩展：83. 删除排序链表中的重复元素

问题描述
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例1

输入：head = [1,1,2]
输出：[1,2]

示例2

输入：head = [1,1,2,3,3]
输出：[1,2,3]

代码

static ListNode deleteDuplicates(ListNode head) {ListNode slow = head;   //慢指针ListNode fast = head;   //快指针while (fast != null) {if (fast.val != slow.val) {slow.next = fast;slow = slow.next;}fast = fast.next;}//slow需要断开后面的元素slow.next = null;return head;
}

27. 移除元素

问题描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例1

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例2

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

代码

static int removeElement(int[] nums, int val) {int fast = 0, slow = 0;while (fast < nums.length) {if (nums[fast] != val) {nums[slow] = nums[fast];slow++;}fast++;}return slow;
}

283. 移动零

问题描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例1

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例2

输入: nums = [0]
输出: [0]

代码

static void moveZeroes(int[] nums) {int slow = 0;int fast = 0;while (fast < nums.length) {if (nums[fast] != 0) {nums[slow] = nums[fast];slow++;}fast++;}//后面的元素用0补齐for (int i = slow ; i < nums.length; i++) {nums[i] = 0;}
}

左右指针

167. 两数之和

问题描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例1

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

示例2

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例3

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

代码1：利用map

static int[] twoSum(int[] nums, int target) {//k：v  被需要的数字：当前数字下标Map<Integer, Integer> needValAndIndexNowMap = new HashMap<>();for (int i = 0; i < nums.length; i++) {//需要的数字出现了if (needValAndIndexNowMap.containsKey(nums[i])) {//第一个数字的下标：needValAndIndexNowMap.get(arr[i])//第二个数字的下标：ireturn new int[]{needValAndIndexNowMap.get(nums[i]), i};}//需要的数字不存在，存入mapneedValAndIndexNowMap.put(target - nums[i], i);}return null;
}

代码2：利用左右指针

static int[] twoSum(int[] nums, int target) {int l = 0;int r = nums.length - 1;while (l < r) {//整体数字偏小，l右移if (nums[l] + nums[r] < target) {l++;//整体数字偏大，r左移} else if (nums[l] + nums[r] > target) {r--;} else {return new int[]{l, r};}}return null;
}

15. 三数之和

问题描述
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

代码

static Set<List<Integer>> threeSum(int[] arr) {//set可以自动去重结果集Set<List<Integer>> result = new HashSet<>();//数据排序Arrays.sort(arr);//以arr[i]为基准数，利用左右指针遍历其他两个值for (int i = 0; i < arr.length; i++) {int l = i + 1;int r = arr.length - 1;while (l < r) {//如果三个数之和小于0，则左指针右移，整体增大if (arr[i] + arr[l] + arr[r] < 0) {l++;//如果三个数之和大于0，则右指针左移，整体减少} else if (arr[i] + arr[l] + arr[r] > 0) {r--;} else {//如果三个数之和等于0，则右指针左移，左指针右移，继续找下一组数据result.add(Arrays.asList(arr[i], arr[l], arr[r]));l++;r--;}}}return result;
}

一个方法团灭 NSUM 问题

344. 反转字符串

问题描述
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例1

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例2

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

代码

static void reverseString(String[] s) {int l = 0;int r = s.length - 1;while (l < r) {String temp = s[l];s[l] = s[r];s[r] = temp;l++;r--;}
}

热身题：回文串判断

static boolean isPalindrome(String s) {char[] chars = s.toCharArray();int l = 0;int r = chars.length - 1;while (l < r) {if (chars[l] != chars[r]) {return Boolean.FALSE;}l++;r--;}return Boolean.TRUE;
}

5. 最长回文子串

问题描述
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例1

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2

输入：s = "cbbd"
输出："bb"

代码

public class LongestPalindromeDemo {private int left;private int len;String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}for (int i = 0; i < s.length(); i++) {// 找到以 s[i] 为中心的回文串find(s, i, i);// 找到以 s[i] 和 s[i+1] 为中心的回文串find(s, i, i + 1);}return s.substring(left, left + len);}void find(String s, int left, int right) {// 防止索引越界while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {//是否最长子串, 是的话更新len, left指针if (right - left + 1 > len) {len = right - left + 1;this.left = left;}// 向两边展开left--;right++;}}
}

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

问题描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

代码

static int lengthOfLongestSubstring(String s) {//双指针：左指针int left = 0;//双指针：右指针int right = 0;//当前长度int length = 0;//最大长度int maxLength = 0;//存放字符串的位置HashSet<Character> set = new HashSet<>();while (right < s.length()) {//set中不包含当前字符if (!set.contains(s.charAt(right))) {set.add(s.charAt(right));length++;if (length > maxLength) {maxLength = length;}right++;} else {//set中包含当前字符，移动左指针，set中进行移除，直到left可以放进去while (set.contains(s.charAt(right))) {set.remove(s.charAt(left));left++;length--;}set.add(s.charAt(right));//这里可以不用判断最大长度，因为左边指针至少移动了一个，而右边正好移动一个，这时候最大长度没有收到影响length++;right++;}}return maxLength;
}

其他类型面试题

11. 盛最多水的容器

问题描述
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例

输入: [1,8,6,2,5,4,8,3,7]
输出: 49

代码

static int maxArea(int[] arr) {int maxArea = 0;int left = 0;int right = arr.length - 1;while (left < right) {//求出此时的面积，如果大于maxArea则替换maxAreamaxArea = Math.max(maxArea, Math.min(arr[left], arr[right]) * (right - left));//如果left小，则left++，if (arr[left] < arr[right]) {left++;} else {right--;}}return maxArea;}

42. 接雨水

问题描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

代码

 static int trap(int[] height) {int len = height.length;int[] left = new int[len];  //左边挡板数组int[] right = new int[len]; //右边挡板数组//找到左边的挡板高度（取决于当前位置左边的最大高度）left[0] = height[0];for (int i = 1; i < height.length; i++) {left[i] = Math.max(left[i - 1], height[i]);}//找到右边的挡板高度（取决于当前位置右边的最大高度）right[len - 1] = height[len - 1];for (int i = len - 2; i > 0; i--) {right[i] = Math.max(right[i + 1], height[i]);}//计算存水量（左右挡板最小高度-当前位置的高度）int res = 0;for (int i = 0; i < height.length; i++) {res += Math.min(left[i], right[i]) - height[i];}return res;}

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

问题描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。

示例

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

代码

   static int[] searchRange(int[] nums, int target) {if (nums == null || nums.length < 1) {return new int[]{-1, -1};}int low = 0;int high = nums.length - 1;//利用二分查找定位while (low <= high) {int mid = (low + high) >> 1;if (nums[mid] < target) {low = mid + 1;} else if (nums[mid] > target) {high = mid - 1;} else {//找到了target所在的位置，以这个位置为中心，（low-high）这个范围左右两边依次查找int left = mid;int right = mid;//找到以后，left--，继续向左查找，如果找到最后一个，则第一个下标位置为 left + 1while (nums[left] == target) {left--;}//找到以后，right++，继续向右查找，如果找到最后一个，则第一个下标位置为 right -1while (nums[right] == target) {right++;}return new int[]{left + 1, right -1};}}return new int[]{-1, -1};}

来源：https://blog.csdn.net/weixin_38896998/article/details/88810177
来源（算法小抄）：https://labuladong.gitee.io/algo/2/20/23/
两数之和（视频讲解）：https://www.bilibili.com/video/BV11C4y1t7iY
三数之和（视频讲解）：https://www.bilibili.com/video/BV1oE411Q7cS
最长回文子串（文字详解）：https://zhuanlan.zhihu.com/p/107792552
无重复字符的最长子串（视频讲解）：https://www.bilibili.com/video/BV113411v7Ak
盛最多水的容器（视频讲解） ：https://www.bilibili.com/video/BV1mJ411M7gE
接水量（视频讲解）：https://www.bilibili.com/video/BV1264y1d76P
接水量（视频讲解）：https://www.bilibili.com/video/BV1Qg411q7ia
接水量（图片来源）https://blog.csdn.net/weixin_45345143/article/details/128178541