删除有序数组中的重复项
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
26 难度：easy
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 ：
输入：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 。不需要考虑数组中超出新长度后面的元素。
提示：
0 <= nums.length <= 3 * 104-104 <= nums[i] <= 104nums 已按升序排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
int i = 0;
int j = 1;
while(j < n){
if(nums[i] == nums[j]){
j++;
continue;
}
if(j != i + 1){
nums[i + 1] = nums[j];
}
i++;
j++;
}
return i + 1;
}
}
|
双指针！原地覆盖！
删除有序数组中的重复项 II
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/
80 难度：mid
与上一题一样，只不过这次要求每个元素 最多出现两次 ，返回删除后数组的新长度。
示例：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if(n <= 2) return n;
int i = 2;
int j = 2;
while(j < n){
if(nums[i - 2] != nums[j]){
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
}
|
删除排序链表中的重复元素II
82 难度 mid
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例1：
1->2->3->3->4->4->5 去重后为 1->2->5
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
迭代，一次遍历
因为头结点也可能被删除，所以需要使用虚拟头结点来跟踪最终的头结点
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 ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode dummyNode = new ListNode();
dummyNode.next = head;
ListNode cur = dummyNode;
while(cur.next != null && cur.next.next != null){
if(cur.next.val == cur.next.next.val){
int x = cur.next.val;
while(cur.next != null && cur.next.val == x){
cur.next = cur.next.next;
}
}else{
cur = cur.next;
}
}
return dummyNode.next;
}
}
|
移除元素
https://leetcode-cn.com/problems/remove-element/
27 难度 easy
给定一个无序数组，需要原地移除所有数值等于val的元素，并返回移除后数组的新长度。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 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]，也会被视作正确答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public int removeElement(int[] nums, int val) {
int n = nums.length;
int i = 0;
int j = 0;
while(j < n){
if(nums[j] != val){
nums[i] = nums[j];
i++;
}
j++;
}
return i;
}
}
|
这个方法和上面的方法基本上一样，都是将需要的元素放在数组的前面位置，即将不等于val的元素覆盖到前面，如果等于val，就跳过这个元素，搜索后面不等于val的元素，覆盖到上面。
i 指向需要被覆盖的元素的位置，j 来遍历数组元素
官方还有一个优化版，利用首尾指针，目的是当出现只有数组首元素等于val的时候，上述方法所有元素都要往前移动，复杂度高，所以可以利用首尾指针，直接将尾指针的元素覆盖到首指针就结束了。
？但是我有一个疑问，待解决。如果数组元素全都是val 那不是还得全部赋值到 i 的位置？这和首元素是val 全部覆盖耗费的时间一样呀？不懂哪里优化了
三数之和
https://leetcode-cn.com/problems/3sum/
15 难度：mid
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [1]
输出：[]
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
for(int k = 0; k < n - 2; k++){
if(k != 0 && nums[k] == nums[k - 1]) continue;
int target = nums[k];
int j = n - 1;
for(int i = k + 1; i < n - 1; i++){
if(i != k + 1 && nums[i] == nums[i - 1]) continue;
while(i < j && nums[i] + nums[j] + target > 0){
j--;
}
if(i == j){
break;
}
if(nums[i] + nums[j] + target == 0){
List<Integer> arr = new ArrayList<>();
arr.add(nums[k]);
arr.add(nums[i]);
arr.add(nums[j]);
list.add(arr);
}
}
}
return list;
}
}
|
根据最接近的三数之和，又写了一个代码，我比较喜欢这个，但是这个比上面那个花费时间多2ms
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
| class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> list = new ArrayList<>();
int n = nums.length;
for(int k = 0; k < n - 2; k++){
if(nums[k] > 0) break;
if(k != 0 && nums[k] == nums[k - 1]) continue;
int j = n - 1;
int i = k + 1;
while(i < j){
int sum = nums[k] + nums[i] + nums[j];
if(sum > 0){
while(i < j && nums[j - 1] == nums[j]){
j--;
}
j--;
}else if(sum < 0){
while(i < j && nums[i + 1] == nums[i]){
i++;
}
i++;
}else{
List<Integer> arr = new ArrayList<>();
arr.add(nums[k]);
arr.add(nums[i]);
arr.add(nums[j]);
list.add(arr);
while(i < j && nums[i + 1] == nums[i]){
i++;
}
i++;
while(i < j && nums[j - 1] == nums[j]){
j--;
}
j--;
}
}
}
return list;
}
}
|
首先需要先确保数组有序，原因是如果无序，则会遍历出重复的一组和为0的数。然后第一层for循环是遍历数组中所有不重复的元素，以它为新数组的首元素，来构造不同的和为零的数组。如果遇到重复的元素，就直接跳过，因为上一步已经遍历过了。然后是数组的第二个元素，指针从上层的后面开始，往右移动，第三个元素从末尾开始，往左移动。当有a+b+c=0后，随着b的增加，要想a+b’+c‘=0，那么一定有 c’ < c。所以c是从数组末尾向左移动。移动移动后…当b与c相等时，在以首元素开头的循环中不会再有和为零的元素了，需要进入新的首元素循环啦
举个栗子🌰
新数组的首元素即是-4，第二个元素从k+1开始，而第三个元素是从n-1开始，只有他们的和大于0时，说明 c 的值太大了，需要缩小，往左移动 j ，才有可能使和为0。而如果他们的和一开始就小于0，那肯定不会有更大的了，需要将 i 向右移动，然后再看是否有和大于等于0的一组数。
最接近的三数之和
https://leetcode-cn.com/problems/3sum-closest/
16 难度 mid
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104
暴力解法
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 threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
for(int k = 0; k < n - 2; k++){
for(int i = k + 1; i < n; i++){
for(int j = i + 1; j < n - 1; j++){
int sum = nums[i] + nums[j] + nums[k];
if(sum == target){
return sum;
}
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
}
}
}
return best;
}
}
|
但是这个方法**时间复杂度是O(n的三次方)**，太高了，可以用双指针来优化
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
| class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
for(int k = 0; k < n - 2; k++){
if(k != 0 && nums[k] == nums[k-1]) continue;
int knum = nums[k];
int j = n - 1;
int i = k + 1;
while(i < j){
int sum = nums[i] + nums[j] + knum;
if(sum == target){
return sum;
}
if(Math.abs(sum - target) < Math.abs(best - target)){
best = sum;
}
if(sum > target){
int j0 = j - 1;
while(i < j0 && nums[j0] == nums[j]){
j0--;
}
j = j0;
}else{
int i0 = i + 1;
while(i0 < j && nums[i0] == nums[i]){
i0++;
}
i = i0;
}
}
}
return best;
}
}
|
一看到最接近，肯定是用差的绝对值来比较，三数的和与target的差的绝对值越小（最小为0），越接近target。我们先固定一个数a，假设下标是i，对剩下两个数用双指针由两端开始进行枚举，范围是【i+1，n-1】，由于数组已经进行了升序排序，a+b+c>=target 则需要减小c，即向左移动c，反之，a+b+c < target 则需要增加b，即向右移动b。
每一次枚举的过程中，我们尝试边界上的两个元素，根据它们与 target 的值的关系，选择「抛弃」左边界的元素还是右边界的元素，从而减少了枚举的范围。 —–LeetCode
有两个可以优化的地方。
- sum==target，直接返回即可
- 对于同一个移动的指针，如果移动的下一个数与移动前的数值相同，那么需要跳过，因为移动前的循环中其他变量都没变，相当于这个也没变，不用重复做了。
- 时间复杂度：O(n²)，for循环是O(n)，while循环也是O(n)
- 空间复杂度：O(log N)。排序
四数之和
https://leetcode-cn.com/problems/4sum/
18 难度 mid
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
- 0 <= a, b, c, d < n
- a、b、c 和 d 互不相同
- nums[a] + nums[b] + nums[c] + nums[d] == target
- 你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
List<List<Integer>> list = new ArrayList<>();
if(n < 4) return list;
Arrays.sort(nums);
for(int k = 0; k < n - 3; k++){
if(k != 0 && nums[k] == nums[k - 1]) continue;
if ((long)nums[k] + nums[k + 1] + nums[k + 2] + nums[k + 3] > target) break;
if ((long)nums[k] + nums[n - 3] + nums[n - 2] + nums[n -1] < target) continue;
for(int m = k + 1; m < n - 2; m++){
if(m != k + 1 && nums[m] == nums[m - 1]) continue;
if ((long)nums[k] + nums[m] + nums[m + 1] + nums[m + 2] > target) break;
if ((long)nums[k] + nums[m] + nums[n - 2] + nums[n -1] < target) continue;
int i = m + 1;
int j = n - 1;
while(i < j){
int sum = nums[i] + nums[j] + nums[k] + nums[m];
if(sum - target > 0){
while(i < j && nums[j] == nums[--j]);
}else if(sum - target < 0){
while(i < j && nums[i] == nums[++i]);
}else{
list.add(Arrays.asList(nums[k],nums[m],nums[i],nums[j]));
while(i < j && nums[j] == nums[--j]);
while(i < j && nums[i] == nums[++i]);
}
}
}
}
return list;
}
}
|
和三数之和一样的思路，只是多加了一层for循环，所以时间复杂度是O(n的三次方)
但是这个优化是我没想到的
// 如果这四数之和大于target, 往后算也必大于target
if ((long)nums[k] + nums[k + 1] + nums[k + 2] + nums[k + 3] > target) break;
// 下面这四数之和小于target, 则nums[i]小了
if ((long)nums[k] + nums[n - 3] + nums[n - 2] + nums[n -1] < target) continue;
合并两个有序数组
https://leetcode-cn.com/problems/merge-sorted-array/
88 难度 easy
给你两个按 非递减顺序 （就是在数组nums1中，前m个元素是递增的，在数组nums2中，元素是递增的）排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
逆向双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
while(j >= 0){
if(i >= 0 && nums1[i] > nums2[j]){
nums1[i + j + 1] = nums1[i];
i--;
}else{
nums1[i + j + 1] = nums2[j];
j--;
}
}
}
}
|
nums2数组优先，如果nums2数组为空时，直接就不用合并了，结束循环，但是nums1为空（指的是m=0）不一定
- 时间复杂度：O(m + n)。指针移动单调递减，最多移动 m+n次。
- 空间复杂度：O(1)。
实现strStr()
https://leetcode-cn.com/problems/implement-strstr/
28 难度 easy
实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
示例 1：
输入：haystack = “hello”, needle = “ll”
输出：2
要看needle是否存在于haystack中，就看haystack中有几个与needle长度相同的字符串，然后依次进行比较，只要一有不同的字符，就立刻开始下一次的比较，这样比较节约时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int strStr(String haystack, String needle) {
int m = haystack.length();
int n = needle.length();
for(int i = 0; i < m - n + 1; i++){
boolean flag = true;
for(int j = 0; j < n; j++){
if(haystack.charAt(i + j) != needle.charAt(j)){
flag = false;
break;
}
}
if(flag){
return i;
}
}
return -1;
}
}
|
还有一个KMP解法，后续学到了再看
删除排序链表中的重复元素
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
83 难度 easy
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
示例1：
1->1->2->3->3 去重后变为 1->2->3
输入：head = [1,1,2,3,3]
输出：[1,2,3]
提示：
- 链表中节点数目在范围
[0, 300] 内
-100 <= Node.val <= 100- 题目数据保证链表已经按升序 排列
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 ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode cur = head;
ListNode next = cur.next;
while(cur != null){
if(next == null){
cur.next = null;
break;
}
if(cur.val != next.val){
cur.next = next;
cur = cur.next;
}
next = next.next;
}
return head;
}
}
|
- 时间复杂度：O(n)O(n)，其中 nn 是链表的长度。
- 空间复杂度：O(1)O(1)。
没有用双指针的解法（官方用的这个解法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null){
return head;
}
ListNode cur = head;
while(cur.next != null){
if(cur.val == cur.next.val){
cur.next = cur.next.next;
}else{
cur = cur.next;
}
}
return head;
}
}
|