Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• Only one valid answer exists.

Follow-up:

Can you come up with an algorithm that is less than O(n2) time complexity?

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut nums: Vec<(usize, i32)> =
						// into_iter(): nums 벡터에 대한 이터레이터를 만들고
						// enumerate(): 이터레이터를 인덱스, 값 쌍으로 이루어진 튜플 생성
						// collect::<Vec<(usize, i32)>>() : 튜플을 다시 벡터로 전환
            nums.into_iter()
                .enumerate()
                .collect::<Vec<(usize, i32)>>();

				// 벡터 (인덱스, 값) 에서 두 번째 값을 기준으로 불안정 정렬
        nums.sort_unstable_by_key(|&(_, n)|n);

				// nums 의 각 원소에 대해 반복하되,
				// enumerate 를 이용해서 인덱스 k 와 원소 (i, ni) 를 튜플로 반환
        for (k, (i, ni)) in nums.iter().enumerate()
        {
						// 인덱스 k 일 때 값 ni 가 선택되었고,
						// &(target - *ni) 는 찾으려는 키 값. 즉 target 과 ni의 차이를 계산한 값.
						// |&(_, nj)| nj : (usize, i32) 튜플에서 두 번째 원소 nj를 추출
            match nums[k+1..].**binary_search_by_key**(&(target - *ni), |&(_, nj)| nj)
            {
								// 이진탐색에 성공할 경우 jj는 찾은 원소의 인덱스
                Ok(jj) => return vec![*i as i32, nums[jj+k+1].0 as i32],
                Err(_) => {}
            }
        }

        unreachable!("Error");
        
        return vec![0,0];
    }
}