Cải tiến bài toán đếm số cặp phần tử trong mảng mà có tổng bằng x

Mình đang cải tiến 1 bài toán có dạng như sau : Nhập n và x rồi nhập n phần tử của mảng, có bao nhiêu cặp A[i] + A[j] == x với i < j. Cách cơ bản là chạy 2 vòng for mình đã làm được rồi nhưng khi nộp quá thời gian. Có bạn nào có thể gợi ý cho mình cách cải tiến được không? Mình chân thành cảm ơn !

Nhiều cách mà bạn. Mà có thể dùng mảng đánh dấu lưu lại các giá trị Ai đã xuất hiện rồi duyệt các Aj để check xem có tồn tại không, có thì tăng biến đếm.
Nếu giá trị lớn quá thì dùng map/set có trong C++ ấy.

3 Likes

Với số x không quá lớn thì có thể đơn giản là dùng mảng để đếm
Gọi mảng đó là count với count[v] = số lần xuất hiện của giá trị v trong mảng A
Như vậy số cặp (x, x-v) là số lượng [cặp có tổng là x] và [một trong 2 số đó có giá trị là v] là count[v] * count[x - v]

3 Likes

Bạn có thể chi tiết không? Cho ví dụ các thứ cho dễ hiểu. Mình cảm ơn !

Lưu ý là : i < j nha. Nếu không có ràng buộc thì mình dùng đếm phân phối rồi. Có thể là bạn đúng, có thể chi tiết không ạ?

thì sao bạn?
bạn đã suy nghĩ kĩ chưa? bạn đã thử cho một ví dụ mẫu rồi tự giải chưa?
bạn có thử giải bình thường không điều kiện và có điều kiện i < j chưa?

3 Likes

Cảm ơn bạn, mình đã thử cách đấy nhưng test có số lớn quá nên không dùng được. Mong bạn có thể góp ý cách khác.

  1. Số quá lớn là bao nhiêu bạn cũng không nói ra thì ai biết mà giúp, ngay cả một cái đề bài và ví dụ đầy đủ còn không có
  2. Giải pháp này là O(n), cách triển khai thì tùy ngôn ngữ và tùy scope của đề bài, nhìn nhìn cũng vẫn là đếm mà thôi.
  3. Mình không thấy bạn thật sự bỏ công sức ra để cố gắng làm bài mà chỉ mong chờ một đáp án, minh chứng là hôm qua chưa gì bạn đã reply lại và xem như mình hiểu sai đề. Và đến hôm nay, bạn chưa show được bất kì thành quả gì mà cũng chỉ phán là gợi ý “không dùng được”. Như vậy thì cần phải có một bài code hoàn chỉnh mới gọi là dùng được?
  4. Người có tinh thần học hỏi thì họ sẽ tìm trăm phương ngàn kế, kể cả đoán công thức, kể cả chạy trâu (hạ sách dùng khi đi thi mà bị bí) để giải một bài toán. Ngày xưa mình đi học cấp 3, có những lúc phải tốn 2 ngày cho một bài tập, thâm chí là có lúc xem bài giải mà không hiểu (vì kể cả cùng 1 concept mà mỗi người code mỗi kiểu nên cũng khó lòng mà hiểu người ta viết gì) thì mình vẫn ghi nhớ nó lại giống như là một cái gì đó lúc rảnh xem lại
  5. Thu hoạch khi giải bài tập chính là kinh nghiệm giải quyết vấn đề, gặp và tránh né được bug linh tinh (số quá lớn, mảng quá lớn, tràn số … bla bla và mấy lỗi vớ vẫn khác). là một quá trình trải nghiệm mà chỉ có thể tự code mới thấu hiểu được. là một quá trình từ concept tới triển khi concept gặp trắc trở gì, giải quyết ra sao.
    Ví dụ như bài này, ý tưởng là như thế nhưng [số phần tử tối đa của mảng], [giá trị tối đa của mỗi phần tử là bao nhiêu] và [x tối đa bao nhiêu], chọn ngôn ngữ gì, những yếu tố này đều ảnh hưởng đến cách triển khai concept như là cấu trúc dữ liệu hay kiểu dữ liệu …
  6. Nói dài dòng vậy thôi chứ mình cũng không có ý gì, chỉ là mình chưa thấy được effort của bạn cho việc học mà thôi. Chúc bạn may mắn.
3 Likes

Bị thế này thì coi lại chỗ này nè bạn

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?