No.219 Contains Duplicate ||

No.219 Contains Duplicate ||

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between iand j is at most k.

输入：给定整数数组和整数k，找出是否存在不同的索引i和j使得nums[i]=nums[j]，且i与j直插最多为k
输出：只要存在，就返回true

典型的使用哈希表。

 1 #include "stdafx.h"
 2 #include <map>
 3 #include <vector>
 4 #include <iostream>
 5 using namespace std;
 6 
 7 class Solution
 8 {
 9 public:
10     bool containsNearbyDuplicate(vector<int> &nums, int k)
11     {//输入：给定整数数组和整数k，找出是否存在不同的索引i和j使得nums[i]=nums[j]，且i与j直插最多为k
12      //只要存在，就返回true
13         int size = nums.size();
14         if(size <= 1 || k==0)
15             return false;
16         k = (k<0 ? -k : k);//取k的绝对值
17         map<int,int> mapping;
18 
19         for(int i=0; i<size; i++)
20         {
21           /*
22             if(mapping.find(nums[i]) == mapping.end())
23                 mapping[nums[i]] = i;//对应的是其下标
24             else
25             {//已存在
26                 if(i - mapping[nums[i]] <= k)
27                     return true;//存在
28                 else
29                     mapping[nums[i]] = i;//更新
30             }
31           */
32             if(mapping.find(nums[i]) != mapping.end() && i - mapping[nums[i]] <= k)
33                 return true;//存在
34             else
35                 mapping[nums[i]] = i;//对应的是其下标,或者更新
36         }
37         return false;
38     }
39 };
40 
41 int main()
42 {
43     Solution sol;
44     int data[] = {1,2,3,4,2,0};
45     vector<int> test(data,data+sizeof(data)/sizeof(int));
46 
47     cout<< boolalpha << sol.containsNearbyDuplicate(test,-5)<<endl;
48     
49 }