[코딩테스트] LeetCode 75 level 1. prefix sum (구간합) - java 풀이 및 연관 문제

오늘은 LeetCode의 코딩테스트 문제를 풀었다.
어떤 순서로 문제를 풀어봐야 할 지 감이 안잡혀서 LeetCode 75 코스를 선택해서 시작해보았다.

LeetCode 75

🍎 724. 문제 풀이

코딩테스트 공부를 시작한 지 얼마되지 않았지만 누적합 문제는 백준 사이트에서 몇 가지를 풀어봤었는데도
이 pivot index 문제는 포인터와 슬라이드의 개념을 확실히 알지 못하면 연관된 문제를 만났을때 어떤 방식으로 풀어나가야 할지 감을 못잡을 것 같아 정리를 해보았다.

public int pivotIndex(int[] nums) { // 포인터 + 슬라이딩 도전
	int total_sum = Arrays.stream(nums).sum(); // 배열 전체 합 - pivot 기준 오른쪽 구간의 합 초기값
	int left_sum = 0; // pivot 기준 왼쪽 구간의 합 초기값
	int pivot = 0; // 구간을 나누는 기준 숫자의 index

	for (int i = 0; i < nums.length; i++) {
		pivot = i;
		total_sum -= nums[i]; // 오른쪽 구간 -1
		if (left_sum == total_sum) // 비교
			return pivot;
		else left_sum += nums[i]; // 왼쪽 구간 +1
	}
    return -1;
}

pivot index 를 기준으로 좌측 구간의 합과 우측 구간의 합이 같아지는 index를 리턴하는 문제이고, 
브루트 포스(이중 for문)로 구하면 시간복잡도가 커지기 때문에 

포인터와 슬라이딩 개념을 사용하여 

1. index가 1개씩 이동함에 따라 (for 문 i가 1씩 커지거나 작아짐)
2. 좌측 구간의 합은 +, (좌측 구간의 합 += i 위치의 배열 원소 값)
3. 우측 구간의 합은 - 를 해주며 (총합 -= i 위치의 배열 원소 값)
4. 두 구간의 합을 비교하면 되는 방법이다. (if 문 좌측 구간의 합 == 우측 구간의 합)

문제 설명