560. Subarray Sum Equals K

class Solution {
    public int subarraySum(int[] nums, int k) {
        //커지면 앞에서 빼주고 작으면 계속 더하기~~~
        //헐 대박...
        if (nums.length <= 1) {
            return (nums[0] == k) ? 1 : 0;
        }
        
        int start = 0;
        int end = 1;
        int sum = nums[start];
        int total = 0;
        while (start <= end) {
            if (start == end) {
                if (end >= nums.length) {
                    start++;
                } else {
                    end++;
                    sum += nums[end];
                }
            } else if (sum == k) {
                total++;
                sum -= nums[start];
                start++;
            } else if (sum < k) {
                sum += nums[end];
                end++;
            } else {
                sum -= nums[start];
                start++;
            }
        }
        
        if (sum == k) {
            total++;
        }
        
        return total; 
    }
}

처음에는 sliding window를 쓰려고 했읍니다..
근데 영 안돼서 생각을 해보니
마이나스..가 있다는점...^^

class Solution {
    public int subarraySum(int[] nums, int k) {
        int result = 0;
        
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    result++;
                }
            }
        }
        
        return result;
    }
}

Runtime: 1233 ms, faster than 17.54% of Java online submissions for Subarray Sum Equals K.
Memory Usage: 41 MB, less than 94.12% of Java online submissions for Subarray Sum Equals K.

그래서 이중포문이로 돌아왔읍니다~
말 그대로 일일이 뒤지는~ 방법~~

루션이

public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer > map = new HashMap < > ();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;
    }
}

Runtime: 17 ms, faster than 95.77% of Java online submissions for Subarray Sum Equals K.
Memory Usage: 41.3 MB, less than 73.90% of Java online submissions for Subarray Sum Equals K.

제 사랑 쉬맵이로 이런거도 할 수 있군요...ㅎㅎ.......

알던 쉬맵이에다가 sum 값을 계속 넣어준다
Key, value ==> sum, frequency
sum 차이로 숫자를 찾는 느낌으루다가!
만약에 sum이 같은 게 나온다면 그 숫자가 될 수 있는 가짓수가 여러개라는 뜻이니 매번 나올때마다 frequency를 업데이트 해줌
그리고 쭉 가면서 만약에 총 sum - k가 전에 나온 적이 있다면
그 바로 앞까지만 더해서 k를 만들 수 있다는 뜻이니 그 숫자가 가능한 frequency 만큼 더해준다

루션이 천재같아요..

냅다외워!!!!