[Leetcode Algorithm I, Day2] [leetcode 283, leetcode 167 ][c++]

한줄평 : 와 오늘문제는 짧지만 아주 뇌를 자극해준다. 

HINT!

two pointer

 

283. Move Zeroes

---

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

 

한줄해석 : 0을 뒤로 옮기되, 숫자 배열을 바꾸지마라.

 

Example 1:

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

HINT : two pointer 

---

# IDEA

two pointer

여태 two pointer 을 left, right로 나누어 좌/우를 탐색하며 한칸씩 전진하는 용도로 사용했었는데, 

여기서는 다음 두 변수를 사용한다. 

1) +1을 통해, 0이 아닌 수로 배열을 채워나가는 lastnonzero

2) lastnonzero 에 넣기위한 값을 찾는 cur 

 

다시말하면, 배열 0이 아닌 수들을 찾아내 앞쪽에서부터 채워(swap)나간다. 

 

class Solution {
public:
    void moveZeroes(vector<int>& nums) {        
       
        for(int lastNonZeroFoundAt=0, cur=0; cur<nums.size();cur++){
            if(nums[cur]!=0)
                swap(nums[lastNonZeroFoundAt++], nums[cur]);         
        }  
    }
};

 

167. Two Sum II - Input Array Is Sorted

---

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

한줄해석 : 두수의 합이 target값이 되는 두수의 인덱스를 찾아 봔한해라

( 솔루션은 1개이고, 배열은 증가하는 순으로 정렬되어있다. 

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

 

# IDEA

two pointer의 속성은 배열내에서 활용 할 수 있는 값이 (index, value 등)  order을 가질때 사용 할 수 있다는 점이다. 

two sum 1에서는 sorted가 아니였기 때문에 unordered_map을 사용하였지만, two sum2에서는 sorted 된 속성을 활용하여 two pointer을 통해 문제를 해결하자. 또한 위 문제에서는 정답이 1개이므로 해당 방법을 사용할 수 있는것 같다. 

 

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l=0;
        int r=numbers.size()-1;
        
        while(l<=r){
            if(numbers[l]+numbers[r]==target)
                return {l+1,r+1};
            else if(numbers[l]+numbers[r]>target)
                r--;
            else
                l++;            
        }
        return {};
    }   
    
};