/// 1. Two Sum (Easy)
///
/// 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?
use leetcode::*;

struct Solution {}

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut nums: Vec<_> = nums.iter().enumerate().collect();
        nums.sort_by(|(_ai, a), (_bi, b)| a.cmp(b));
        let mut i = 0usize;
        let mut k = nums.len() - 1;
        let mut result = Vec::new();
        loop {
            if nums[i].1 + nums[k].1 == target {
                break;
            } else if nums[i + 1].1 + nums[k].1 <= target {
                i += 1;
            } else {
                k -= 1;
            }
        }
        result.push(nums[i].0 as i32);
        result.push(nums[k].0 as i32);
        result
    }
}

pub fn main() {
    println!("{:?}", Solution::two_sum(arg_into(1), arg_into(2)))
}

#[cfg(test)]
mod tests {
    use crate::Solution;
    use leetcode::vi;

    #[test]
    fn test() {
        assert_eq!(Solution::two_sum(vi("[2,7,11,15]"), 9), vi("[0,1]"));
        assert_eq!(Solution::two_sum(vi("[3,2,4]"), 6), vi("[1,2]"));
        assert_eq!(Solution::two_sum(vi("[3,3]"), 6), vi("[0,1]"));
    }
}