<Hard> Contains Duplicate III (LeetCode : C#)

https://leetcode.com/problems/contains-duplicate-iii/

📕 문제 설명

정수 배열과 두 정수 indexDiff, valueDiff가 주어질 때 다음의 조건을 만족하는 pair (i,j) 존재 여부 반환

1) i != j
2) |i - j| <= indexDiff
3) |nums[i] - nums[j]| <= valueDiff

• Input
  정수배열, indexDiff, valueDiff
• Output
  조건 만족하는 pair (i,j) 존재 여부

예제

시도 1.

안될것 같았지만 우선 첫 시도는 완전 탐색으로 구현했다.

O(N^2) 완전 탐색

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {

        for (int i = 0; i < nums.Length - 1; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (j - i <= indexDiff && Math.Abs(nums[j] - nums[i]) <= valueDiff)
                {
                    return true;
                }
            }
        }

        return false;
        
    }
}

풀이

보니까 indexDiff만큼만 j를 돌려도 되겠어서 수정하니까 통과되었다.

public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {

        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j <= i + indexDiff; j++)
            {
                if (j >= nums.Length) continue;
                if (Math.Abs(nums[j] - nums[i]) <= valueDiff)
                {
                    return true;
                }
            }
        }

        return false;
        
    }
}

결과