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

• 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>();

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;

pre = cur;
}
return false;
}

• Great solution. Thanks for sharing

• 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;