219. 存在重复元素II

滑动窗口

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        /**
         * 滑动窗口
         * i为左指针，right为右指针，当区间长度小于k时且不满足条件，right右移
         * 当长度为k还不满足条件，i右移，同时right从i + 1开始
         */
        for (int i = 0; i < nums.length; i++) {

            int right = i + 1;

            while (right - i <= k && right < nums.length){

                if (nums[i] == nums[right]){
                    return true;
                }
                else {
                    right++;
                }
            }
        }

        return false;
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

优化1——使用集合存储元素，避免重复判断

import java.util.HashSet;

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {

        /**
         * 滑动窗口
         * i为左指针，right为右指针，当区间长度小于k时且不满足条件，right右移
         * 当长度为k还不满足条件，i右移，同时right从i + 1开始
         * 用set存储元素，当在k的范围内出现重复元素时返回true，否则删除存储的第一个元素
         */
        HashSet set = new HashSet<>();

        for (int i = 0; i < nums.length; i++) {

            if (set.contains(nums[i])){
                return true;
            }

            set.add(nums[i]);

            if (set.size() > k){
                set.remove(nums[i - k]);
            }
        }

        return false;
    }
}


/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */


https://leetcode-cn.com/problems/contains-duplicate-ii/

						  
					  
						
							


						

							
							
			LeetCode滑动窗口数组							
						



						

						
						


						

						
					
					

					
					

						
相关

						

				
						
			

																
								

										
剑指 Offer 59 - I. 滑动窗口的最大值

									
									

								 

        

								

							
							

																
								

										
java中常用数组copy方法

									
									

								 

        

								

							
							

																
								

										
数组基础，稀疏数组，冒泡排序

									
									

								 

        

								

							
							

																
								

										
数组的输入与输出（三）【用指针变量指向数组元素】

									
									

								 

        

								

							
							

																
								

										
数组的输入与输出（一）【下标法】

									
									

								 

        

								

							
							

																
								

										
【LeetCode每日一题】员工的重要性

									
									

								 

        

								

							
							

																
								

										
【LeetCode每日一题】整数反转

									
									

								 

        

								

							
							

																
								

										
如何根据key合并数组中的对象

									
									

								 

        

								

							
							

																
								

										
Stream流，集合与基本数组的相互转换

									
									

								 

        

								

							
							

																
								

										
【LeetCode】—— 翻转二叉树

									
									

								 

        

								

							
							

																
								

										
最大数maxnumber - 题解【树状数组】

									
									

								 

        

								

							
							

																
								

										
旋转数组的最小数字

									
									

								 

        

								

							
							
            
            
            
                                    
           
  			
						

					

					
				

				

														
					
					

					
									

					
									   
标签

										

										
    
										

									

										
										

									

					

					
				


			
		
		
		
			


						





	

	
一品网 冀ICP备14022925号-6