java数据结构刷题练习

class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);for(int i=1;i<nums.length;i++){if(nums[i-1]==nums[i])return true;}return false;
}
}作者：affectionate-albattani7tn
链接：https://leetcode.cn/problems/contains-duplicate/solution/pai-xu-xun-huan-by-affectionate-albattan-bvdp/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：

输入：nums = [1]
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray
著作权归领扣网

class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;for(int num: nums) {if(sum > 0) {sum += num;} else {sum = num;}ans = Math.max(ans, sum);}return ans;}
}作者：guanpengchn
链接：https://leetcode.cn/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

络所有。商业转载

class Solution {（优化见下面）public int maxSubArray(int[] nums) {int ans = nums[0]; // 记录当前最大子序和int cur = nums[0]; // 记录当前连续子序列的和for (int i = 1; i < nums.length; i++) {if (nums[i] <= 0 && cur <= 0)cur = nums[i]; // 如果当前元素小于等于 0，且前面的连续子序列的和也小于等于 0，则以当前元素更新连续子序列的起点else if (nums[i] <= 0)cur = cur + nums[i]; // 如果当前元素小于等于 0，但前面的连续子序列的和大于 0，则将当前元素加入连续子序列中，因为加入后整体变大else if (nums[i] >= 0 && cur <= 0)cur = nums[i]; // 如果当前元素大于 0，且前面的连续子序列的和小于等于 0，则以当前元素更新连续子序列的起点else if (nums[i] >= 0 )cur = nums[i] + cur; // 如果当前元素大于 0，且前面的连续子序列的和也大于 0，则将当前元素加入连续子序列中，加入后更大ans = Math.max(cur,ans); // 更新当前最大子序和}return ans; // 返回当前最大子序和}
}作者：eyi-gu-bi-gu-e
链接：https://leetcode.cn/problems/maximum-subarray/solution/yi-yan-kan-dong-you-qian-ru-shen-by-eyi-sr9nn/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

请联系官方授权，非商业转载请注明出处。

题目3

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
 

示例 1：

输入：nums = [1,2,3,1]
输出：true
示例 2：

输入：nums = [1,2,3,4]
输出：false
示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contains-duplicate
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {public int[] twoSum(int[] nums, int target) {int key;for (int i = 1; i < nums.length; ++i) {key = target - nums[i];for (int j = 0; j < i; ++j) {if (nums[j] == key) return new int[]{i, j};}}return null;}
}作者：jiang-cu-san-wen-yu
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-bao-li-mei-ju-ha-xi-bia-vtce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (map.containsKey(target - nums[i])) {return new int[]{map.get(target - nums[i]), i};}map.put(nums[i], i);}return null;}
}作者：jiang-cu-san-wen-yu
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-bao-li-mei-ju-ha-xi-bia-vtce/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

题目四

给你两个按 非递减顺序 排列的整数数组 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 中的元素。
示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
 

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public void merge(int[] nums1, int m, int[] nums2, int n) {/* 双指针利用nums1和nums2已经升序排列的，每次从两个数组第一个元素取出较小的放入结果数组时间复杂度O(m+n),指针需要移动m+n次，空间复杂度O(m+n),需要建立一个新数组存储，最后再把结果赋值到nums1 */int p1 = 0;int p2 = 0;int[] sorted = new int[m+n];int cur;while (p1 < m || p2 < n) {if (p1 == m) {// 如果p1已经走完，后续的cur都是nums2的元素cur = nums2[p2++];} else if (p2 == n) {// 如果p2已经走完，后续的cur都是nums1的元素cur = nums1[p1++];} else if (nums1[p1] < nums2[p2]) {// 如果p1 p2都没走完，cur为两者较小的值cur = nums1[p1++];} else {// 如果p1 p2都没走完，cur为两者较小的值cur = nums2[p2++];}// 将cur赋值给排序结果值对应的下标元素，注意这里的-1和上面的p1++ p2++sorted[p1 + p2 - 1] = cur;}// 额外的空间重新赋值给nums1for (int i = 0; i < m + n; i++) {nums1[i] = sorted[i];}
}作者：s1amduncan
链接：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-s1amdu-xfeq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二
public void merge(int[] nums1, int m, int[] nums2, int n) {// 逆向双指针，上述双指针之所以用临时变量，是因为如果直接合并到nums1中，从前往后，// 但是实际nums1后半部分是空的0占位，// 直接覆盖不会影响结果，因此指针可以设置从后往前遍历，每次取两则较大值放入nums1的后面，// 时间复杂度O(m+n),指针移动单调递减最多移动m+n次，空间复杂度O(1)，直接对nums1原址修改,不需要额外的空间int p1 = m - 1; // nums1的指针起始位置int p2 = n - 1; // nums2的指针起始位置int tail = m + n - 1; // 合并后的nums1的指针起始位置int cur; // 当前指针需要赋值的元素// 如果p1或p2没有往前走到头，则不断循环while (p1 >= 0 || p2 >= 0) {if (p1 == -1) {// 如果nums1的指针走到头，即nums1的元素都已经取出cur = nums2[p2--];} else if (p2 == -1) {// 如果nums2的指针走到头，即nums2的元素都已经取出cur = nums1[p1--];} else if (nums1[p1] > nums2[p2]) {// nums1和nums2都没取完，选择两个较大的加入到tailcur = nums1[p1--];} else {// nums1和nums2都没取完，选择两个较大的加入到tailcur = nums2[p2--];}// 将当前cur值赋值给tail后,tail往前移动一位nums1[tail--] = cur;}
}作者：s1amduncan
链接：https://leetcode.cn/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-s1amdu-xfeq/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。