删除有序数组中的重复项
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] <= 104
nums
已按升序排列
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; } }
|