523.Continuous Subarray Sum

Posted on | In

Test Cases

1
2
3
4
5
6
7
8
9
10
[1,5]
-6
[23, 2, 4, 6, 7]
6
[23 ,2, 4, 6, 7]
0
[0, 0]
0
[0, 0]
100

Solution 1: accepted 29%

Time: O(n^2)
Brute force with double loops

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public boolean checkSubarraySum(int[] nums, int k) {
        int len = nums.length;
        if (len < 2)
          return false;
        // Only if all elements in nums are 0, can k be 0
        if (k == 0) {
          for (int n : nums) {
            if (n != 0)
              return false;
          }
          return true;
        }
        // Double loop to check all possible combinations
        for (int i = 0; i < len - 1; i++) {
          int sum = nums[i];
          for (int j = i + 1; j < len; j++) {
            if ((sum + nums[j]) % k == 0)
              return true;
            sum += nums[j];
          }
        }
        return false;
    }