Java O(n) using HashSet (not HashMap) with clear explanation


  • 1
    R

    Inspired by https://discuss.leetcode.com/topic/80793/java-o-n-time-o-k-space/18, my solution only uses HashSet rather than HashMap. The only difference is the way to exclude the cases where a single number is a multiple of k, which can be done by checking whether its previous is also a multiple of k. Here is my solution with explanation.

    public boolean checkSubarraySum(int[] nums, int k) {
    	/**
    	 * rangeSum + mod: if rangeSum(0, i)%k == rangeSum(0, j)%k, for
    	 * i<i+1<j, then rangeSum(i+1, j)%k==0, and return true.
    	 * 
    	 * Use a set to store rangeSum(0, i)%k, if it appears again, then
    	 * check whether the length of the continuous subarray (i+1, j) is
    	 * >=2. Notice that if the length is 1, then i+1=j, and so
    	 * nums[j]%k==0, we may use this to check. To tell whether
    	 * i+1==j, we can check whether nums[j]%k==0 and nums[j-1]%k==0 or
    	 * not.
    	 */
    
    	int n = nums.length;
    	if (n < 2)
    		return false;
    
    	if (k == 0) {
    		for (int i = 1; i < n; i++)
    			if (nums[i] == 0 && nums[i - 1] == 0)
    				return true;
    		return false;
    	}
    
    	int sum_remain = nums[0] % k;
    	HashSet<Integer> remains = new HashSet<Integer>();
    	remains.add(0);
    	remains.add(sum_remain);
    
    	int pre = sum_remain, cur;
    	for (int i = 1; i < n; i++) {
    		cur = nums[i] % k;
    		if (cur == 0) {
    			// if nums[i-1]%k==0
    			if (pre == 0)
    				return true;
    
    			// otherwise, if there was a continuous subarray 
    			// in nums[0, i-1] satisfies, then it would have 
    			// been returned before
    
    			pre = cur;
    			continue;
    		}
    
    		sum_remain = (sum_remain + cur) % k;
    		if (remains.contains(sum_remain))
    			return true;
    		remains.add(sum_remain);
    
    		pre = cur;
    	}
    	return false;
    }
    

  • 0
    C

    Great solution. Thanks for sharing


  • 0
    A

    Concise solution using only Set

        public boolean checkSubarraySum(int[] nums, int k) {
            Set<Integer> seen = new HashSet<>();
            int runningSum = 0;
            int buff = 0;
            for (int i=0; i < nums.length; i++) {
                runningSum = runningSum + nums[i];
                if (k != 0) runningSum %= k;
                if (seen.contains(runningSum)) return true;
                seen.add(buff);
                buff = runningSum;
            }
            return false;
        }
    

Log in to reply
 

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