Leetcode 532) K-diff Pairs in an Array

24 May 2021 in Algorithms

• k==0일 때의 코드, map에 넣어서 중복인 것 카운트 해준다.
• 그 외의 경우에는, Collections.sort()를 이용해 정렬을 한 후 수를 세준다.
• 다른 방법에서도 sort를 먼저 해주고, 그 후에 while문으로 풀었다.

class Solution {
    public int findPairs(int[] nums, int k) {
        int cnt=0;
        Map<Integer,Integer> m = new HashMap<>();
        if(k==0){
            for(int item :nums){
                if(!m.containsKey(item)){                             
                    m.put(item,1);

                }else{
                    int val=m.get(item);
                    m.put(item,++val);
                }
            }
        for (int key : m.keySet()) {
            if(m.get(key)>1){
                cnt++;
            }
        }            
            return cnt;
        }
        
        
        List<Integer> l = new ArrayList<>();

        for(int item : nums){       
            if(!l.contains(item)){
                l.add(item);
            }
        }    
        
        Collections.sort(l);
        int j=0;
        for(int i=0;i<l.size();i++){
            while(l.get(i)>=l.get(j)+k){
                if(l.get(i)==l.get(j)+k){
                    cnt++;                    
                }
                j++;
                if(j==l.size()-1){
                    return cnt;
                }
            }
        }
        return cnt; 
    }
}

다른 방법

class Solution {
    public int findPairs(int[] nums, int k) {
        Arrays.sort(nums);

        int left = 0, right = 1;
        int result = 0;

        while (left < nums.length && right < nums.length) {
            if (left == right || nums[right] - nums[left] < k) {
                //left 와 right가 같아질 때, 혹은 원소의 차가 k보다 작을 경우 right를 움직인다.
                right++;      
            } else if (nums[right] - nums[left] > k) {
                //차가 k보다 클 경우, left를 움직인다.(찾는 값이 없다.)
                left++;       
            } else {
                // 차가 k일 경우, left를 움직이고 result에 추가해준다. 
                left++;
                result++;
                //중복되는 숫자에서 벗어나기 위한 while문.
                while (left < nums.length && nums[left] == nums[left - 1])
                    left++;
            }
        }
        return result;        
    }
}