167. Two Sum II - Input Array Is Sorted

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Table of Contents

1. Cách tiếp cận vấn đề

Bài này giống tương tự bài 1. Two Sum trước đó, tuy nhiên một chút sự khác biệt làm cho bài toán này khó hơn đó chính là việc ta không được sử dụng bất kỳ bộ nhớ ngoài nào như map để lưu lại giá trị num cùng vị trí index của nó, nhưng bù lại mảng input sẽ được sắp xếp theo thứ tự tăng dần.

Và tận dụng tính chất đơn điệu của dãy số tăng dần, ta sẽ sử dụng kỹ thuật 2 pointers để tìm ra được 2 vị trí mà tại đó tổng của chúng bằng target đã cho.

2. Solution & Phân Tích

Ta sẽ sử dụng 2 con trỏ, 1 con trỏ left ở đầu mảng, 1 con trỏ right nằm ở cuối mảng, với mỗi cặp giá trị mà 2 con trỏ đang nắm giữ, ta sẽ tính sum của cặp giá trị đó, nếu:

• Giá trị sum này nhỏ hơn target: ta cần tăng con trỏ left để nó trỏ đến phần tử có giá trị lớn hơn, từ đó làm tăng giá trị của sum và có cơ hội tìm ra được target.
• Giá trị sum này lớn hơn target: tương tự với con trỏ right nhưng ta cần giảm nó để nó trỏ đến phần tử có giá trị nhỏ hơn, từ đó làm giảm giá trị của sum và có cơ hội tìm ra target.
• Còn nếu giá trị sum bằng với target thì xin chúc mừng bạn đã tìm ra được đáp án 😆 ta chỉ cần trả về vị trị index mà 2 con trỏ đang nắm giữ là được. Lưu ý cần cộng thêm 1 vào 2 index này, vì index mà ta dùng bắt đầu từ 0, còn theo đề bài thì tính từ 1, vì vậy nên mới có sự chênh lệch 1 đơn vị.

Sau cùng nếu vị trí của con trỏ left vượt qua con trỏ right thì chương trình dừng lại và không có cặp nào thỏa mãn yêu cầu. Tuy nhiên trong phạm vi bài toán này thì không xảy ra điều đó do bài toán luôn đảm bảo sẽ có ít nhất 1 cặp kết quả cho mỗi test input.

Time-Complexity: O(n)

Space-Complexity: O(1)

Với n là số lượng các phần tử trong mảng input.

3. Code