why my solution is wrong ?


  • 0

    Although my solution`s time complexity is O(N^3), I want to know why it is wrong.

    public class Solution {
    	public int findPairs(int[] nums, int k) {
    		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    		for (int i = 0; i < nums.length; i++) {
    			for (int j = i + 1; j < nums.length; j++) {
    				if (Math.abs(nums[i] - nums[j]) == k) {
    					if (map.containsKey(nums[i]) && map.get(nums[i]) != nums[j]) {
    						map.put(nums[j], nums[i]);
    					} else if (!map.containsKey(nums[i]) && !map.containsValue(nums[i])) {
    						map.put(nums[i], nums[j]);
    					} else if (!map.containsKey(nums[i]) && map.containsValue(nums[i])) {
    						boolean flag = true;
    						for(Integer val : map.keySet()){
    							if(val.equals(nums[j])){
    								flag = false;
    							}
    						}
    						if(flag){
    							map.put(nums[i], nums[j]);
    						}
    					}
    				}
    			}
    		}
    		return map.size();
    }
    

    }


  • 0
    D

    @张昕.
    I run similar code before and failed too. Then I find the reason.
    In some cases, the entry in map will be overwritten, so the the number of unique k-diff pairs will be incorrect.
    E.g, consider below situation, k = 2:
    (3, 1)
    (5, 7) pairs are already in map
    then when (3, 5) is found, this pair (3, 5) will put in map as (5, 3) according to your code, then (5, 7) will be replaced by (5, 3).
    FYI.


  • 0

    @detective0922
    wow,thanks a lot. I realized my fault finally. It troubled me for a long time,thank you very much


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.