数组题之存在重复元素专题
我一直以为leetcode的数组题是给人签到用的，结果发现一般只有一个数组的题目，都是不让你用O(N^2)暴力过的，得优化到O(nlogn)或者最好O(n)。
存在重复元素
217. 存在重复元素
难度简单
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
想要特地用滑动窗口(i前面的用TreeSet保存，由于题目没有设置答案不能距离nums[i]多远，所以无需维护TreeSet的长度，也即滑动窗口的长度就是[0,i])：
class Solution {
public boolean containsDuplicate(int[] nums) {
//滑动窗口，借助TreeSet实现O（nlogn）
int length = nums.length;
TreeSet<Integer> ts = new TreeSet<>();
for(int i = 0;i < length;i++){
if(ts.contains(nums[i])){
return true;
}
ts.add(nums[i]);
}
return false;
}
}
是可以过的，O(nlogn)的复杂度。
但是想测试不用TreeSet的滑动窗口（[j,i]）：
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
if(length == 0){
return false;
}
for(int i = 0;i < length;i++){
for(int j = 0;j < i;j++){
if(nums[i] == nums[j]){
return true;
}
}
}
return false;
}
}
然后就熟悉的超限了。。。
考虑到这题只需要检查重复元素即可，那就排序后直接判断是否与前一个元素相等就行了：
class Solution {
public boolean containsDuplicate(int[] nums) {
Arrays.sort(nums);
int length = nums.length;
if(length == 0){
return false;
}
for(int i = 1;i < length;i++){
if(nums[i] == nums[i-1]){
return true;
}
}
return false;
}
}
这样就是O(n)。
存在重复元素2
219. 存在重复元素 II
难度简单
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1
输出: true
示例 3:
输入: nums = [1,2,3,1,2,3], k = 2
输出: false
滑动窗口yyds
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
//滑动窗口
int length = nums.length;
HashMap<Integer,Integer> hm = new HashMap<>();//<值，下标>
for(int i = 0;i < length;i++){
if(hm.containsKey(nums[i]) && i - hm.get(nums[i]) <= k){
return true;
}
hm.put(nums[i],i); //起到记录和覆盖的两个作用
}
return false;
}
}
窗口为：[0,i]。
（曾想过动态规划，但是建立不出状态转移方程，所以就没法做。）
存在重复元素3
220. 存在重复元素 III
难度中等
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。
如果存在则返回 true，不存在返回 false。
示例 1：
输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
示例 3：
输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
提示：
0 <= nums.length <= 2 * 104-231 <= nums[i] <= 231 - 10 <= k <= 1040 <= t <= 231 - 1
一开始以为很简单，然后就被教育了。这题主要是卡你两个地方：1. nums[i]-nums[j]可能会很大，大到超出int范围（两个int数相加减一定要考虑溢出的问题），解决方法就是用Long或者BigInteger（后来发现BigInteger实在大题小做，而且BigInteger使用不方便）。2. nums的长度可能会很大，比如一个测试用例长这样：
[2433,3054,9952,6470,2509,8502,-8802,-5276,6559,-9555,-4765,6399,6543,2027,1723,-3032,-3319,-7726,-1425,-7431,-7492,4803,7952,-6603,-784,-8011,6161,-6955,5800,5834,-6310,1097,2327,-4007,8664,-9619,5922,518,9740,9976,4257,-7803,6023,4189,-5167,-4699,2441,5941,3663,625,5402,-3447,8888,9040,-4811,-7547,6822,1415,9372,-9262,4584,4149,-276,-4019,198,608,-4466,5383,7871,3149,-8358,9270,3565,-882,-9494,-6475,9833,-7744,-598,5299,5976,7361,-9444,3771,-5718,9051,3469,-4028,4216,5506,-8611,-9744,-8007,213,-3454,-2420,6283,-5616,-3508,-1329,4694,-7219,2056,9063,-9648,-7722,-755,-4422,-9878,-5104,3344,4585,-6871,7970,-2867,-9631,-579,-7948,-7035,-6526,-7549,-4731,-4163,-5796,-97,7385,-7460,-925,-7538,18,7781,-6875,9067,3350,668,5070,8965,9204,-6108,5337,9710,5218,-4764,1369,-180,157,-3261,-843,2881,-6371,570,3832,6948,-6861,-3604,7183,-5271,-4031,-611,-4958,5115,188,5433,3273,6251,6943,5446,-6114,-3257,-6265,-6810,-5000,-4493,-2496,-7071,-5923,4855,9865,-5402,-9373,1309,-8436,-6972,1117,79,-4448,-5354,5109,-9729,1057,9207,9074,-7036,-1878,2614,1559,-4723,-4969,-2667,2641,1401... 82793 more chars
//我还删减了好多。。。这个用例长度长达8万
//我以为解决了大数溢出就行了。。。结果，压根不能for(for(length))这样遍历
import java.math.BigInteger;
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int length = nums.length;
for(int i = 0;i < length;i++){
for(int j = i+1;j < length;j++){//用例有一个十万长度数组过不去
System.out.println("0");
if(nums[i] < 10000000 && nums[j] < 10000000){
if(Math.abs(nums[i]-nums[j]) <= t && Math.abs(i-j) <= k){
System.out.println("1");
return true;
}
}
else {
System.out.println("2");
BigInteger res1 = new BigInteger(nums[i]+"");
BigInteger res2 = new BigInteger(nums[j]+"");
BigInteger rest = new BigInteger(t+"");
if(res1.subtract(res2).abs().compareTo(rest) <= 0 && Math.abs(i - j) <= k){//[-2147483648,2147483647]会计算爆栈变成负数，
// System.out.println("i="+i+" j="+j);
// System.out.println("res="+res1+" Math.abs(nums[i] - nums[j])="+Math.abs(res1)+" Math.abs(i - j)="+Math.abs(i - j));
return true;
}
}
}
}
return false;
}
}
//后来看了滑动窗口解法后不甘心，又尝试了下暴力的滑动窗口，还是无法过巨长长度的数组的测试用例
import java.math.BigInteger;
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int length = nums.length;
for(int i = 0;i < length;i++){
for(int j = i-1;j >= 0 && j >= i-k;j--){//用例有一个十万长度数组过不去
// System.out.println("0");
if(nums[i] < 10000000 && nums[j] < 10000000){
if(Math.abs(nums[i]-nums[j]) <= t && Math.abs(i-j) <= k){
// System.out.println("1");
return true;
}
}
else {
// System.out.println("2");
BigInteger res1 = new BigInteger(nums[i]+"");
BigInteger res2 = new BigInteger(nums[j]+"");
BigInteger rest = new BigInteger(t+"");
if(res1.subtract(res2).abs().compareTo(rest) <= 0 && Math.abs(i - j) <= k){//[-2147483648,2147483647]会计算爆栈变成负数，
// System.out.println("i="+i+" j="+j);
// System.out.println("res="+res1+" Math.abs(nums[i] - nums[j])="+Math.abs(res1)+" Math.abs(i - j)="+Math.abs(i - j));
return true;
}
}
}
}
return false;
}
}
看了宫水三叶的题解才发现诸如数组比较判断的题，直接暴力搜索是不行的，一旦长度达到十万就会超限了，必须考虑O(nlogn)/O(n)的解法。比如滑动窗口+O(logn)查找复杂度的数据结构：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int length = nums.length;
//题目的意思是在[i-k,i]范围内([i-k,i+k]太大，反正是遍历i所以只需要取前一段)，是否存在[nums[i]-t,nums[i]+t]的nums[j]。
//TreeSet是有序集合，放进去了就自动排序。
TreeSet<Long> ts = new TreeSet<>();
for(int i = 0;i < length;i++){
Long res1 = ts.floor(nums[i]*1L);//小于等于nums[i]的最大值
Long res2 = ts.ceiling(nums[i]*1L);//大于等于nums[i]的最小值
if(res1 != null && nums[i] - res1 <= t){
return true;
}
if(res2 != null && res2 - nums[i] <= t){
return true;
}
ts.add(nums[i]*1L);
if(i >= k){
ts.remove(nums[i-k]*1L);//由于i是从0开始遍历的，所以i-k前面的TreeSet全部不要，就不会出现abs(nums[i] - nums[j]) <= t但是abs(i - j) >= k的情况了。
}
}
return false;
}
}
桶排序，有点烧脑，不是我能想到的：
class Solution {
long size;
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
int length = nums.length;
Map<Long,Long> map = new HashMap<>();//桶排序，每个桶是该下标对应的+-t范围,比如u下标，那么map.get(u)要是不为null就说明[u-t,u+t]有元素，只要维护这个表的长度不超过t即可。
size = t+1L;
for(int i = 0;i < length;i++){
long u = nums[i] * 1L;
long index = getIndex(u);
if(map.get(index) != null){
return true;
}
//检查相邻的桶，表示-t和+t这个范围，这个是重点，为什么要检查相邻的桶存不存在呢？因为getIndex()这个方法里，num/size后，处于[num-size,num+size]的数/size，会落入[num/size-1]、[num/size]、[num/size+1]这三个桶内。为啥？计算一下就知道了：2/3=0，3/3=1，4/3=1，5/3=1,6/3=2,7/3=2,10/3=3，处于[4-3,4+3]也即[1,7]的数，比如6，一定在6/3=2的2或者1或者3这个桶内，所以只需要查找这三个桶就能判断是否存在[num-size,num+size]的数了，再维护数量不超过k，就可以实现题目的意思。
long l = index-1,r = index+1;
if(map.get(l) != null && u - map.get(l) <= t){
return true;
}
if(map.get(r) != null && map.get(r) - u <= t){
return true;
}
map.put(index,u);
if(i >= k){
map.remove(getIndex(nums[i-k]*1L));
}
}
return false;
}
//由数值本身计算出桶排序的下标
long getIndex(long num){
return num >= 0 ? num/size : (num+1)/size-1;
}
}
总结：
对于题目的大数，一般不需要用到BigInteger类，只需要用Long即能解决大部分int溢出问题。 int转long只需要*1L或者+1L。
数组的滑动窗口解法很实用，但是滑动窗口也不能暴力搜，需要借助数据结构TreeSet实现O(logn)查找。
桶排序太高深了暂时不看了，精华在于getIndex。
每天一个无用小知识（不用也不会看，用到了百度就行）
HashMap的使用
判断有无一个键：hashmap.containsKey(“xxx”);
判断有无一个值：hashmap.constainsValue(“xxx”);
根据特定Key获取Value：HashMap.get(Key);
不能通过值直接获取键。
哪个是键哪个是值？：new HashMap<键，值>();