[LeetCode/Hard] 220. Contains Duplicate III

1. Input

1) int[] nums

2) int indexDiff

3) int valueDiff

 

2. Output

1) 다음 조건을 만족하는 두 정수가 있다면 true, 없다면 false를 반환

// 조건: 서로 다른 i, j에 대해

- abs(i - j) <= indexDiff

- abs(nums[i] - nums[j]) <= valueDiff

 

3. Constraint

1) 2 <= nums.length <= 10^5

2) - 10^9 <= nums[i] <= 10^9

3) 1 <= indexDiff <= nums.length

4) 0 <= valueDiff <= 10^9

 

4. Example

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0 -> Output: true

설명: abs(nums[0]-nums[3]) <= 0이고, abs(0-3)<=3이므로 true를 반환한다.

 

5. Code

1) 첫 코드(2023/01/23)

boolean answer = false;
if(nums.length==2){
    answer = Math.abs(nums[0]-nums[1])<=valueDiff;
} else{
    for(int i=0 ; i<nums.length-1 ; i++)
        for(int j=i+1 ; j<=Math.min(i+indexDiff,nums.length-1) ; j++)
            if(Math.abs(nums[i]-nums[j])<=valueDiff){
                answer = true; break;
            }
}
return answer;

- 역시나 성능은 별로다.