力扣刷题合集：力扣刷题_Sunlightʊə的博客-CSDN博客
217.存在重复元素
相关题目链接：力扣 - 存在重复元素
题目重现
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
思路
首先，这个题目中涉及到每个元素出现的次数，这时就可以考虑使用哈希了。其次，当我们将这个数组进行排序后，我们会发现，相同的元素一定是相邻的，所以我们也可以采用排序的方法来解决这道题。
哈希
哈希的方式很简单，只需要遍历一遍数组并将数组元素存放在哈希表中即可，注意存放元素时要先与已经在哈希表中的元素进行对比，如果当前元素已经在哈希表中存在，就代表这个元素是重复的。
排序
排序后，我们可以知道，相同的元素它们一定是相邻的。
这样的话，我们只需要将数组排序后，遍历数组，寻找下标为i的元素与下标为i+1的元素是否相同即可（注意，这里的i从0开始）。
代码
哈希
class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int x : nums) {if (!set.add(x)) {return true;}}return false;}
}排序
class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 1; i++) {if (nums[i] == nums[i + 1]) {return true;}}return false;}
}53.最大子数组和
相关题目链接：力扣 - 最大子数组和
题目重现
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
思路
这里我们采用动态规划的方法。
首先，我们确定maxAns(i)表示以第i个数据结尾的连续子数组的最大和。
那么对于整个数组，我们可以求出在每个位置的maxAns(i)，然后在这些maxAns(i)中选出最大的那个连续子数组的最大和。那么，现在的问题就来到了如何求每个位置的maxAns(i)。
我们可以想到，对于连续子数组的最大和，有两种递推公式：一种是maxAns(i-1)+nums[i]表示nums[i]加入当前连续子序列和。另一种是nums[i]表示从头开始计算当前子序列的和。我们要求的就是其中的最大数，也就是说maxAns=max（maxAns(i-1)+nums[i]，nums[i]）;
代码
class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}
