기억하고싶은것들

Given an integer array nums, 

you need to find one continuous subarray that if you only sort this subarray in ascending order, 

then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

integer 배열인 nums가 주어진다.

하나의 연속적인 sub배열을 구해라,

그 sub배열의 조건은 오직 그 sub배열을 정렬했을 때 전체 배열이 오름차순으로 정렬되는 것이다.

가장 짧은 sub 배열의 길이를 반환해라.

배열에 해당하는 문제이다.

풀이 방식으로는 두개의 포인터를 맨 앞 맨뒤에 두고,

하나씩 순회하면서 정렬기준에 맞지 않는 인덱스를 찾으면 된다.

맨 처음 포인터의 경우, 뒤에 값이 앞에 값보다 작아지는 순간부터의 최솟값의 인덱스를 찾으면 된다.

후에 해당 인덱스의 값이 배열에 어느 위치로 정렬되어야 하는지 찾아야 한다.

맨 뒤의 포인터도 위의 방식과 유사하게 진행하면 된다.

    public int findUnsortedSubarray(int[] nums) {
        boolean found = false;
        int min = Integer.MIN_VALUE;
        for (int i = 1; i <= nums.length - 1; i++) { // find minimum

            if (!found) {
                if (nums[i] < nums[i - 1]) {
                    found = true;
                    min = nums[i];
                }
            } else { // find minimum
                if (min >= nums[i]) {
                    min = nums[i];
                }
            }
        }

        int l = 0;
        if (!found) {
            return 0;
        } else { // find start index
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > min) {
                    break;
                }
                l++;
            }
        }

        found = false;
        int max = Integer.MAX_VALUE;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (!found) {
                if (nums[i] > nums[i + 1]) {
                    found = true;
                    max = nums[i];
                }
            } else {
                if (max <= nums[i]) {
                    max = nums[i];
                }
            }
        }
        int h = nums.length - 1;

        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] < max) {
                break;
            }
            h--;
        }

        return h - l + 1;
    }

해당 풀이로는 시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.

Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.

양수로 이루어진 배열 nums와 양수 integer target이 주어진다.

target보다 크거나 같은 연속적인 서브 배열의 길이를 구해라, 단 길이는 최소한이어야 한다.

만약 조건에 만족하는 서브 배열이 없는 경우에는 0을 반환하라.

주어진 배열에서 타겟보다 크거나 같은 서브 배열의 합의 길이를 구하는 문제이다.

해당 조건을 만족하는 여러개의 서브 배열이 존재할 수 있지만, 그중에서 가장 길이가 짧은 내역을 반환하면 된다. 

배열을 for문을 돌며 sum이 target보다 커지는 시점을 찾고,

해당 시점에서 idx가 0부터 sum을 빼며 길이를 짧게 하며 조건을 만족하는지 찾아보도록 하자.

중간중간 조건이 만족할 때마다, 해당 시점의 서브  배열의 길이를 체크하며 최솟값을 찾도록 하자.

    public int minSubArrayLen(int target, int[] nums) {

        int idx = 0;
        int rst = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];

            if (sum >= target) {
                // make shorter of idx
                rst = Math.min(rst, i - idx + 1);
                sum -= nums[idx];
                idx++;
                while (sum >= target) {
                    rst = Math.min(rst, i - idx + 1);
                    sum -= nums[idx];
                    idx++;
                }
            }
        }
        return rst == Integer.MAX_VALUE ? 0 : rst;
    }

Given an array of integers nums, calculate the pivot index of this array.

The pivot index is the index where the sum of all the numbers strictly to the left of the index is equal to the sum of all the numbers strictly to the index's right.

If the index is on the left edge of the array, then the left sum is 0 because there are no elements to the left. This also applies to the right edge of the array.

Return the leftmost pivot index. If no such index exists, return -1.

integer 배열 nums가 주어지고, "pivot" 인덱스를 해당 배열에서 찾아라.

"pivot" 인덱스는 해당 인덱스를 기준으로 오른쪽 배열의 값들의 합과 왼쪽 배열의 값들의 합이 같은 경우를 말한다.

만약, 배열의 첫 번째 인덱스가 pivot이라면 왼쪽 배열의 합은 0이다, 왜냐하면 왼쪽에는 아무 배열도 없기 때문이다.

오른쪽도 마찬가지다.

가장 왼쪽에 위치하는 pivot 인덱스를 반환하라. 만약 존재하지 않는다면 -1을 반환하라.

우선 주어진 배열의 모든 값들을 더해서 totalSum으로 가지고 있고

하나의 포인터를 0번째 인덱스 기준으로 잡아 , 해당 포인터를 오른쪽으로 이동하며 totalSum에서 빼며 

움직인 요소들의 합과 값을 비교하는 식으로 문제를 해결해보자 ( Sliding ) 

    public int pivotIndex(int[] nums) {
        int totalSum = Arrays.stream(nums).sum();
        int leftSum = 0;
        int pivot = 0;

        for (int i = 0; i < nums.length; i++) {

            pivot = i;
            totalSum -= nums[i];

            if (totalSum == leftSum) {
                return pivot;
            }
            leftSum += nums[i];
        }

        return -1;
    }

하나의 포인터를 기준으로 sliding 방식으로 문제 해결 

A peak element is an element that is strictly greater than its neighbors.

Given an integer array nums, find a peak element, and return its index.

If the array contains multiple peaks, return the index to any of the peaks.

You may imagine that nums[-1] = nums[n] = -∞.

You must write an algorithm that runs in O(log n) time.

"peak"는 양 옆의 숫자들보다 큰 경우를 말한다.

integer 배열 nums가 주어진다, 해당 배열에서 peak을 찾고 그 인덱스를 반환하라.

만약 배열에 여러게의 peak이 존재한다면, 어떠한 인덱스를 반환해도 된다.

배열 밖의 범위의 요소는 가장 작은 수로 인지하라 ( 즉, 맨 처음, 맨 뒤 인덱스의 값은 바로 옆 하나의 이웃보다 크면 peak이 된다)

반드시 시간 복잡도가 O(log n) 인 알고리즘을 작성하라.

배열의 search 알고리즘 문제의 시간 복잡도가 O(log n) 를 만족하기 위해서는 Binary Search를 사용해야 한다. 

결국 peak은 배열의 가장 큰 숫자를 찾으면 된다. 가장 크기 때문에 양옆의 숫자들보다 크기 때문이다.

배열의 가장 큰 숫자를 binary search로 찾는 문제로 생각하고 풀어보자.

    public int findPeakElement(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (right > left) { // binary search 
            int pivot = (left + right) / 2;
            if (nums[pivot] < nums[pivot + 1]) {
                left = pivot + 1;
            } else {
                right = pivot;
            }
        }
        return right;
    }

문제출처 : 

https://leetcode.com/problems/find-peak-element/