TL,DR: Khả năng cao là không có giải pháp tuyến tính nào đẹp đâu, chắc là bạn nhớ sai đề bài, hoặc là thằng tác giả nó cà chớn ở đâu đó rồi.
Giải thích dài dòng hơn thì có lẽ không có giải pháp thời gian tuyến tính thực sự (vì về cơ bản nó đòi hỏi bạn phải tìm được số liền sau của mỗi số, mà điều này về cơ bản có nghĩa là bạn cần phải sắp xếp) nhưng đây là một trong những bài toán khó chịu mà rất khó để chứng minh một giới hạn dưới chính xác. Một vấn đề với việc chứng minh là các chi tiết của nó phụ thuộc rất nhiều vào mô hình bạn đang sử dụng.
Vì bạn đang nói về tổng, bạn không thể lập luận theo các mô hình so sánh đơn giản nhất. Bài toán này chỉ có ý nghĩa nếu các phần tử của mảng là các số thuộc loại nào đó. Sau đó, tất cả các lập luận đều phụ thuộc vào những số đó có thể là gì và bạn có thể làm gì với chúng.
Trong một số trường hợp, bài toán có một giải pháp thời gian tuyến tính. Ví dụ, nếu các số là số nguyên có kích thước đa thức theo độ dài của mảng, bạn có thể sử dụng RadixSort cơ số n để sắp xếp chúng trong thời gian tuyến tính và sau đó sử dụng phương pháp hai con trỏ. (Đây là một giả định khá thực tế trong thực tế, vì bạn có thể dễ dàng sắp xếp bất kỳ mảng số nguyên 64 bit nào trong bốn lần RadixSort. Cách tiếp cận tương tự cũng hoạt động cho các số float sử dụng O(log n) bit để lưu trữ mỗi số.)
Trong các trường hợp không thuộc loại trên, các số trở nên lớn đến mức các phép toán trên chúng nên bắt đầu tính đến một phân tích độ phức tạp thời gian chính xác, vì vậy nó còn khó chịu hơn nữa.
Cuối cùng, một vấn đề kỹ thuật: Lưu ý rằng việc phát biểu bài toán theo các cặp (chỉ số, giá trị) hơi kỳ lạ, vì nó không thay đổi bất cứ điều gì. Bài toán có thể được phát biểu tương đương theo một mảng thông thường. Ví dụ, ví dụ của bạn có thể được phát biểu là “tìm hai chỉ số i, j trong A = [20,80,90,40,60,40,100] sao cho A[i]+A[j] <= k và lớn nhất với ràng buộc này”. Các chỉ số “khác” chỉ là một sự xao nhãng không quan trọng.